On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote:
> 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).
Also it misses a few useful optimizations, such as median-of-three
partitioning. For descriptions of that and other ways to speed
up quicksort, see Sedgewicks "Algorithms in C" or "Algorithms in Pascal"
(I'm afraid Sedgewick didn't write an "Algorithms in Haskell" ;-).
--
Fergus Henderson <[EMAIL PROTECTED]> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED] | -- the last words of T. S. Garp.
