5
\$\begingroup\$

The following code is part of my practice in implementing algorithms in Haskell. I'm aware that bubble sort is a bad choice for sorting sequences in real applications.

import Test.QuickCheck
import Data.List (sort)

-- Going from left to right, swaps two adjacent elements if they are not in order.
-- After the first go, the largest element in the list has bubbled up to the end
-- of the list. In the next go, we start swapping from the first element to the
-- penultimate element and so forth.
bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = go xs (length xs -1)
  where go xs limit | limit > 0 = let swapped = swapTill xs limit in
                                  go swapped (limit -1)
                    | otherwise = xs

-- Swaps adjacent elements in a list if they are not in order, until a limit.
-- After this, the largest elements, from limit to (length xs),
-- are sorted at the list's end.
swapTill :: (Ord a, Num p) => [a] -> p -> [a]
swapTill xs limit = go xs 0
  where go xs count | count < limit = swap xs
                    | otherwise = xs
                      where swap [x] = [x]
                            swap (x:y:xs) | x < y     = x : (go (y:xs) (count +1))
                                          | otherwise = y : (go (x:xs) (count +1))

-- Tests
bubbleSortWorks :: [Int] -> Bool
bubbleSortWorks xs = bubbleSort xs == sort xs

runQuickCheck = quickCheck bubbleSortWorks

I'd very much appreciate hints on how to make this implementation shorter (maybe using a fold) and/or more readable.

\$\endgroup\$
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 5 → 4. \$\endgroup\$ – 200_success Jul 11 '18 at 17:25
  • \$\begingroup\$ In my style of learning Haskell, I do not import Data.List and other weird stuff i don't know about. I first learn to operate from its basic primitives this language is so different that importing libraries will only dilute the learning process into chaotic descent \$\endgroup\$ – eigenfield Apr 6 at 6:41
  • \$\begingroup\$ @typelogic: The only function I use from Data.List is sort. This is used in runQuickCheck to make sure that my bubbleSort produces correct output. The testing code stands apart from the code that I wanted to have reviewed. \$\endgroup\$ – Matthias Braun Apr 6 at 8:02
8
\$\begingroup\$

Here's your shortening including a fold.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = foldr swapTill xs [1..length xs-1]

swapTill :: Ord a => Int -> [a] -> [a]
swapTill 0 = id
swapTill count = \(x:y:xs) -> min x y : swapTill (count-1) (max x y:xs)

Reordering the swaps to sort a growing suffix of the list banishes Int.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort = foldr swapTill []

swapTill x [] = [x]
swapTill x (y:xs) = min x y : swapTill (max x y) xs
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Edited my answer, thank you again to @typelogic for pointing out that my original only worked for a single pass. And since fixing it would have made my answer too close to his original posting, I decided to switch it up to make it a more readable version for beginners!

bubbleUp :: (Ord a) => [a] -> [a]
bubbleUp [] = []
bubbleUp [x] = [x]
bubbleUp (x:y:xs) = smaller : bubbleUp (larger : xs)
  where
    smaller = min x y
    larger = max x y

bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort l = foldl (\acc _ -> bubbleUp acc) l [0 .. length l]

The fold uses the list to be sorted as the accumulator, and each iteration it will do a single bubbleUp, and the acc gets "passed on" to get bubbled up on again. This happens length l times to really make sure each item is where it belongs.

I challenge you to speed it up, there are early exit conditions for bubbleSort (namely a single pass with no swaps), and you can shrink down the search space as items get sorted!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I tested, this is not working. \$\endgroup\$ – eigenfield Apr 6 at 6:38
  • \$\begingroup\$ Hey @typelogic , can you send the data you are running it on to cause it to not work? I’ll confirm on my side. \$\endgroup\$ – kevin meyers Apr 7 at 10:34
  • 1
    \$\begingroup\$ asciinema.org/a/EbRRcpmsFexWRn95QpXTq0lmb \$\endgroup\$ – eigenfield Apr 7 at 21:01
  • \$\begingroup\$ Thanks @typelogic you're absolutely correct, I guess what I wrote was a bubblePass, which only handles one pass. I will update it promptly, ideally I will write it with only the one parameter of the list. \$\endgroup\$ – kevin meyers Apr 7 at 23:33
2
\$\begingroup\$

Below is my attempt to arriving at a more readable and more elegant bubble sorting in Haskell:

main = undefined 

doit []  = []
doit [x] = [x]
doit (x:xs) | x > head xs = head xs:doit (x:tail xs)
            | otherwise = x:doit xs 

bubbleSort xs = foldl (\acc e -> doit acc) xs xs

You requested a shorter version, so the above is short. You requested the use of fold, so the above uses fold. I personally approach Haskell as like doing an mathematical algebra. No redundant formulas, and strive for the most minimal, most readable.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Nov 19 '18 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.