Walter Bright Wrote: > dsimcha wrote: > > == Quote from Walter Bright ([email protected])'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 :-)
