你能将冒泡排序表述为幺半群或半群吗？

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

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;dr冒泡排序是插入排序，是对有序列表的幺半群进行合并的幺半群“粉碎”。

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

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)

因为插入正是将一个单例列表与另一个列表合并。 （合并排序是通过构建平衡树，然后执行相同的 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.