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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
