koldfront

Bubble sort, recursive, in Haskell #haskell #programming

I asked an LLM to spit out an implementation of recursive bubble sort and it kept regurgitating code that didn't work.

That made me want to write a recursive bubble sort in Haskell. It took me a, to be honest slighly embarrassing long, while to come up with a way to write it, so I'm putting it here:

bubbleSort :: [Int] -> [Int]
bubbleSort (x:xs) | bubble (x:xs) == (x:xs) = x:xs
                  | otherwise               = bubbleSort (bubble (x:xs))

bubble :: [Int] -> [Int]
bubble (x:xs) | null xs      = [x]
              | x <= head xs = x : bubble xs
              | otherwise    = head xs : bubble (x : tail xs)

The first function is the ending condition: if bubbling doesn't change the list, we are done. Otherwise, bubble the list and test again.

Bubbling is simple as well, if the first element is smaller than or equal to the second element, keep the first element and bubble the rest of the list.

On the other hand, if the first element is larger than the second, the resulting list is the second element followed by bubbling the first element and the rest of the list.

Here is a Haskell snippet to try it out:

main :: IO ()
main = print (bubbleSort [5, 4, 8, 1, 3, 2, 9, 7])