你可以将Bubble排序为幺半群或半群吗？ [英] Can you formulate the Bubble sort as a monoid or semigroup?
问题描述
$ $ p $
procedure bubbleSort（A：可排序项目列表）
重复
交换=假
对于i = 1到长度（A） - 1包含do：
/ *如果这对错误* /
如果A [i- 1]> A [i]然后
/ *交换它们并记住更改的内容* /
swap（A [i-1]，A [i]）
swapped = true
end if
结束为
直到未交换
结束过程
这里是将Bubble Sort作为Scala的代码
def bubbleSort [T]（arr：Array [T]）（implicit o：Ordering [ T]）{
import o._
val consecutiveIndices =（arr.indices，arr.indices drop 1）.zipped
var hasChanged = true
do {
hasChanged = false
consecutiveIndices foreach {（i1，i2）=>
if（arr（i1）> arr（i2））{
hasChanged = true
val tmp = arr（i1）
arr（i1）= arr（i2）$ （hasChanged）
}
} }
} >
这是Haskell的实现：
bsort :: Ord a => [a] - > [a]
bsort s = case _bsort s of
t | t == s - > t
|否则 - > bsort t
其中_bsort（x：x2：xs）| x> x2 = x2：（_ bsort（x：xs））
|否则= x：（_ bsort（x2：xs））
_bsort s = s
有可能将此形式表述为一个monoid或semigroup？
tl; dr bubblesort是插入排序是monomeric的crush，用于合并排序列表的monoid。
有序列表形成一个monoid。
newtype OL x = OL [x]
实例Ord x => Monoid（OL x）其中
mempty = OL []
mappend（OL xs）（OL ys）= OL（merge xs ys）其中
合并[] ys = ys
合并xs [] = xs
合并xs @（x：xs'）ys @（y：ys'）
| x< = y = x：合并xs'ys
|否则= y：合并xs ys'
插入排序由
给出 isort :: Ord x => [x] - > OL x
isort = foldMap（OL。pure）
因为插入正好合并一个单例列表与另一个列表。 （Mergesort是通过构建一棵平衡树来给出的，然后做同样的foldMap。）
这与bubblesort有什么关系？插入排序和bubblesort具有完全相同的比较策略。如果您将其作为从比较和交换框构成的排序网络，则可以看到这一点。在这里，数据向下流动，对箱子[n]的输入降低：
| | | |
[1] | |
| [2] |
[3] [4]
| [5] |
[6] | |
| | | |
如果按照上述编号给出的顺序执行比较，您将获得插入排序：第一个插入不需要比较;第二需要比较1;第三个2,3;最后4,5,6。
但是，如果您切入\切片......
| | | |
[1] | |
| [2] |
[4] [3]
| [5] |
[6] | |
| | | |
...您正在做bubblesort：首先通过1,2,3;第二通4,5;最后一次传球6。
Given the following pseudocode for the bubble-sort
procedure bubbleSort( A : list of sortable items )
repeat
swapped = false
for i = 1 to length(A) - 1 inclusive do:
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
Here is the code for Bubble Sort as Scala
def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) {
import o._
val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped
var hasChanged = true
do {
hasChanged = false
consecutiveIndices foreach { (i1, i2) =>
if (arr(i1) > arr(i2)) {
hasChanged = true
val tmp = arr(i1)
arr(i1) = arr(i2)
arr(i2) = tmp
}
}
} while(hasChanged)
}
This is the Haskell implementation:
bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
t | t == s -> t
| otherwise -> bsort t
where _bsort (x:x2:xs) | x > x2 = x2:(_bsort (x:xs))
| otherwise = x:(_bsort (x2:xs))
_bsort s = s
Is it possible to formulate this as a monoid or semigroup?
I'm using my phone with a poor network connection, but here goes.
tl;dr bubblesort is insertion sort is the monoidal "crush" for the monoid of ordered lists with merging.
Ordered lists form a monoid.
newtype OL x = OL [x]
instance Ord x => Monoid (OL x) where
mempty = OL []
mappend (OL xs) (OL ys) = OL (merge xs ys) where
merge [] ys = ys
merge xs [] = xs
merge xs@(x : xs') ys@(y : ys')
| x <= y = x : merge xs' ys
| otherwise = y : merge xs ys'
Insertion sort is given by
isort :: Ord x => [x] -> OL x
isort = foldMap (OL . pure)
because insertion is exactly merging a singleton list with another list. (Mergesort is given by building a balanced tree, then doing the same foldMap.)
What has this to do with bubblesort? Insertion sort and bubblesort have exactly the same comparison strategy. You can see this if you draw it as a sorting network made from compare-and-swap boxes. Here, data flows downward and lower inputs to boxes [n] go left:
| | | |
[1] | |
| [2] |
[3] [4]
| [5] |
[6] | |
| | | |
If you perform the comparisons in the sequence given by the above numbering, cutting the diagram in / slices, you get insertion sort: the first insertion needs no comparison; the second needs comparison 1; the third 2,3; the last 4,5,6.
But if, instead, you cut in \ slices...
| | | |
[1] | |
| [2] |
[4] [3]
| [5] |
[6] | |
| | | |
...you are doing bubblesort: first pass 1,2,3; second pass 4,5; last pass 6.
这篇关于你可以将Bubble排序为幺半群或半群吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
