[Haskell-cafe] Bubble sort algorithm implementations (Haskell vs. C)

[Mark Lentczner]

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.

	- Mark

P.S.: Code and driver Main files can be found here:
	http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/


Mark Lentczner
http://www.ozonehouse.com/mark/
IRC: mtnviewmark