> The tutorial defines:
>
> quicksort [] = []
> quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs,
>y>=x]
>
> This code strikes me as twice as slow as it could be because it seems to
> requires two loops through the list on each recursive call.
I guess it is only included in the tutorial in order to demonstrate the
use of list comprehensions. You are right, the definition has several
drawbacks (besides the fact that quicksort (aka slowsort) is _really_ a
bad sorting algorithm).
o it traverses the list twice,
o it has a space leak (xs is alive until the second traversal is done),
o it uses (++) to catenate the results of the recursive calls (note that
(++) takes time proportional to the length of its first argument).
The standard library offers `partition'.
> qsort2 :: (Ord a) => [a] -> [a]
> qsort2 [] = []
> qsort2 (a : as) = qsort2 l ++ a : qsort2 r
> where (l, r) = partition (>= a) as
qsort2 still uses (++); use accumulating arguments to eliminate them
(see Paulson, ML for the working programmer).
> qsort4 :: (Ord a) => [a] -> [a] -> [a]
> qsort4 [] x = x
> qsort4 [a] x = a : x
> qsort4 (a : as) x = partition [] [] as
> where
> partition l r [] = qsort4 l (a : qsort4 r x)
> partition l r (b : bs)
> | b <= a = partition (b : l) r bs
> | otherwise = partition l (b : r) bs
The grand final: Lennart Augustsson's variant. Note that `qsort4'
ist not stable. By duplicating the code we obtain a stable variant
(it additionally takes an ordering predicate as an argument).
> qsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
> qsort (<=) [] y = y
> qsort (<=) [a] y = a:y
> qsort (<=) (a:x) y = qpart (<=) a x [] [] y
@qpart@ partitions and sorts the sublists. Note that @l@ and @r@
are in reverse order and must be sorted with an anti-stable sorting.
> qpart (<=) a [] l r y = rqsort (<=) l (a : rqsort (<=) r y)
> qpart (<=) a (b:x) l r y
> | a <= b = qpart (<=) a x l (b:r) y
> | otherwise = qpart (<=) a x (b:l) r y
@rqsort@ is as @qsort@ but anti-stable, ie reverses equal elements.
> rqsort :: (a -> a -> Bool) -> [a] -> [a] -> [a]
> rqsort (<=) [] y = y
> rqsort (<=) [a] y = a:y
> rqsort (<=) (a:x) y = rqpart (<=) a x [] [] y
> rqpart (<=) a [] l r y= qsort (<=) l (a : qsort (<=) r y)
> rqpart (<=) a (b:x) l r y
> | b <= a = rqpart (<=) a x (b:l) r y
> | otherwise = rqpart (<=) a x l (b:r) y
Hope this helps.
Ralf
PS: If you are interested in sorting algorithms take a look at
http://www.cs.uni-bonn.de/~ralf/PQSort.ps.gz
The paper is a latexed email that contains a collection of (good)
sorting algorithms ;-).
