Daniel de Kok wrote:
On 2009-12-18 20:39:08 +0100, Walter Bright <[email protected]>
said:
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.
But it does have one nice property: due to laziness, the n-th elements
of the sorted array can be found without sorting the full array (except
of course, the largest two n's).
According to what I've read while looking into the subject, whether the
concatenations are lazy or not depends on the language and a number of
implementation vagaries.
Even assuming perfect, overhead-free laziness and ignoring the cost of
all allocations and concatenations, in the worst case (reverse sorted
array) just seeing the top 1 smallest element requires O(n*n) work. It's
an uphill battle finding anything good about functional qsort. It's bad
through and through.
(For solving the selection problem there are better methods - all use
mutation and are very difficult to express in a functional language.)
Andrei
