www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: Go rant

Walter Bright Wrote:

 dsimcha wrote:
 == Quote from Walter Bright (newshound1 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.

Ironically, I think you could write a nearly identical approach in D. By using array slicing, you could get something like Haskell's elegant syntax but still be sorting the array in-place.
 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 :-)

Dec 21 2009