3
\$\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\$
6
\$\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
\$\endgroup\$
0
\$\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.

\$\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.