dsimcha wrote:
== Quote from Walter Bright (newshou...@digitalmars.com)'s article
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
prominently featured in Haskell's official introduction page:
http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
Ain't that cool? But look closer. The advantage of quicksort is that it
is an *in-place* sort. The Haskell one creates new arrays for every
state in the sort.
I think this can be optimized out in theory, though I have no idea how often it
is
in practice.
I'm very doubtful it can be optimized out in theory. I'll bet it isn't
done in practice.
The other fundamental problem with the Haskell
version is that it selects the first array element as the "pivot". This
is the worst choice, since arrays to be sorted tend to already be mostly
sorted, and quicksort gives quadratic performance to sort an already
sorted array with the first element as the pivot.
True. All you'd need to remedy this, though, is a median of 3 function.
Then it's not looking so simple and elegant anymore :-)
