On Tuesday, 17 May 2016 at 17:31:47 UTC, Andrei Alexandrescu
wrote:
We should take advantage of the improved partition code I
discussed at ACCU. Also there's a person on
https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/ discussing a simpler algorithm based on a couple of additional assumptions.
...
Interesting optimization, I hope you don't mind if I use it for
my implementation of Quicksort. However, I would like to suggest
another improvement that I devised a while back.
One shortcoming I find in most implementations of partition is
the unnecessary swapping of elements equal to the pivot resulting
in much unneeded work. The code in your slides has this same
shortcoming. Imagine, for some reason, you call a pivot on an
array full of zeroes. It's going to be moving lots of elements
around for no good reason.
The obvious solution is to simply skip over equal elements but
that is not enough. Reconsider the array full of zeroes; if you
simply skip over all equal elements on the first pass, then the
pivot will end up at the very front or end of the array. Ideally,
at least when sorting, you want the pivot to occur as close to
the center as possible.
My solution is to alternate between incrementing "lo" and "hi"
only one step at a time, skipping over equal elements in the
process. A priori, with an array full of zeroes, the pivot ends
up in the center. Only once you find an element that belongs in
the other partition do you fall back to the Hoare partition
scheme and increment the other iterator until you find another
element to swap with, but do not skip over equal elements in this
case! Otherwise, you can trigger the same behavior as before with
quadratic running time.
Anyways, my solution can be found at the link below. It can be
over twice as fast in an ideal case, but when applied to real
world data with lots of duplicate elements, maybe 5-10% faster.
https://github.com/Xinok/XSort/blob/master/xsort/introsort.d#L171
I don't claim credit for this technique. Admittedly I haven't
really tried looking around to see if anybody else has come up
with the same solution but I'm probably not the first.
