On 12/16/10 9:05 PM, Russel Winder wrote:
On Thu, 2010-12-16 at 20:36 -0600, Craig Black wrote:
It was brought to my attention that the quick sort has a very bad worst
case, so I implemented a simple fix for it. Now the worst case (completely
ordered) is the best case, and it only slows down the general case by a
small percentage. I thought to myself, "it can't be this easy to fix quick
sort". Does anyone see a flaw in this simple fix? Performs much better
than Phobos in completely random and completely sorted data. Perhaps there
is another case where it doesn't do as well?
Is there any reason to not just follow Bentley and McIlroy,
``Engineering a Sort Function,'' SP&E 23(11), p.1249-1265, November
1993. It is what the Java folk and the Go folk do for sorting arrays
(and slices in Go). The Java folk use a modified Merge Sort for sorting
collections. It's all to do with stability as well as algorithmic
complexity.
Quicksort and Merge Sort is, however, a research industry so it will
undoubtedly be the case that there is significantly more work done in
the last 17 years. This is especially true for parallel sorting. A
library for D undoubtedly needs both a sequential and a parallel sort
function. The Go folk haven't tackled this yet, and I can#t see the C++
and Java folk tackling it for the forseeable future even though it is
basically a necessity.
I have no doubt that people on this list could easily contribute to the
research activity in this area, and perhaps that is what some would like
to do, but to tinker away at algorithms outside the context of all the
research work done on this seems like the fastest way to be treated as
amateur hackers.
Yeah, when reading this I was like, "the last sentence ain't likely to
be as well received as others". :o) All - let's take it easy.
I implemented std.algorithm sort and it reuses partition(), another
algorithm, and uses Singleton's partition of first, middle, last
element. I also eliminated a few obvious risks of quadratic behavior.
See comment on line 3831:
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L3808
I was familiar at the time with Bentley's paper but there is only so
much time to spend on implementing one algorithm when I had fifty others
on my plate. I think std.algorithm.sort does an adequate job but it can
be improved in many ways.
Andrei
