digitalmars.D - Re: Go rant
- Kevin Bealer <kevinbealer gmail.com> Dec 21 2009
Walter Bright Wrote:dsimcha wrote:== Quote from Walter Bright (newshound1 digitalmars.com)'s articleqsort (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