koldfront

Bubble sort, recursive, in Haskell #haskell #programming

๐Ÿ•˜๏ธŽ - 2024-01-14

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])

Add comment

To avoid spam many websites make you fill out a CAPTCHA, or log in via an account at a corporation such as Twitter, Facebook, Google or even Microsoft GitHub.

I have chosen to use a more old school method of spam prevention.

To post a comment here, you need to:

ยน Such as Thunderbird, Pan, slrn, tin or Gnus (part of Emacs).

Or, you can fill in this form:

+=