Project: better partition

[Xinok via Digitalmars-d]

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.