[Haskell-cafe] Bubble sort algorithm implementations (Haskell vs.
markl at glyphic.com
Sun Mar 21 03:21:44 EDT 2010
You might express the algorithm more directly in Haskell, without the reverse calls:
bubblesort :: (Ord a) => [a] -> [a]
bubblesort  = 
bubblesort (x0:xs) = case bubble x0 xs of
(xs', True) -> bubblesort xs'
(xs', False) -> xs'
where bubble x1 (x2:xs) | x1 <= x2 = merge x1 False $ bubble x2 xs
| otherwise = merge x2 True $ bubble x1 xs
bubble x1  = ([x1], False)
merge x s (xs, s') = (x:xs, s || s')
Here, the local bubble function does the job of bubbling a value through, and the merge function handles both rebuilding the new, bubbled list, and the swap flag. The case expression in bubblesort is a direct expression in Haskell of "bubble through the list once, and if we swapped anything, do it again".
This version clocks in at about 35% faster than your original.
P.S.: Code and driver Main files can be found here:
More information about the Haskell-Cafe