gpt4 book ai didi

sorting - 你能把冒泡排序表述为一个幺半群或半群吗?

转载 作者:行者123 更新时间:2023-12-04 16:24:26 25 4
gpt4 key购买 nike

给定以下冒泡排序的伪代码

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

这是冒泡排序作为 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)
}

这是 Haskell 的实现:
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

是否可以将其表述为幺半群或半群?

最佳答案

我正在使用网络连接不佳的手机,但可以。

tl;博士气泡排序是插入排序是对有序列表的幺半群进行合并的幺半群“粉碎”。

有序列表形成一个幺半群。

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'

插入排序由下式给出
isort :: Ord x => [x] -> OL x
isort = foldMap (OL . pure)

因为插入正是将单例列表与另一个列表合并。 (Mergesort 是通过构建平衡树,然后执行相同的 foldMap 来给出的。)

这与冒泡排序有什么关系?插入排序和冒泡排序具有完全相同的比较策略。如果将其绘制为由比较和交换框组成的排序网络,则可以看到这一点。在这里,数据向下流动,框 [n] 的下输入向左移动:
| | | |
[1] | |
| [2] |
[3] [4]
| [5] |
[6] | |
| | | |

如果按照上述编号给出的顺序进行比较,将图表切割成/切片,则得到插入排序:第一次插入不需要比较;第二个需要比较1;第三个 2,3;最后的 4,5,6。

但是,如果相反,您切入\切片...
| | | |
[1] | |
| [2] |
[4] [3]
| [5] |
[6] | |
| | | |

...您正在做冒泡排序:首先通过 1,2,3;第二遍4,5;最后一关 6。

关于sorting - 你能把冒泡排序表述为一个幺半群或半群吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21877572/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com