Go rant
Kevin Bealer
kevinbealer at gmail.com
Mon Dec 21 13:30:37 PST 2009
Walter Bright Wrote:
> dsimcha wrote:
> > == Quote from Walter Bright (newshound1 at 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 :-)
More information about the Digitalmars-d
mailing list