Can you formulate the Bubble sort as a monoid or semigroup?

Question

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?

Pennell

you can (e.g.) create a monoid over "ordered sets" and use sort (sort.(++)) as monoid composition operator, but "formulate bsort as a monoid" is not clear for me – Labannah

Answer 1

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.

Blakeslee