Consider defining a function that partitions a range around a given
index like this:
size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot);
Returns x, one of the the indexes that r[pivot] would have if r were
sorted. Also, r[0 .. x] contains stuff no greater than r[x] and r[x + 1
.. $] contains stuff no less than r[x].
The challenge is to implement such a function with fairness: if several
elements are equal to r[pivot], return the index closest to r.length / 2.
The function should be efficient, minimize calls to less and swap, etc.
A variant that is efficient but does not implement fairness is below.
Andrei
size_t pivotPartition(alias less = (a, b) => a < b, Range)
(Range r, size_t pivot)
{
assert(pivot < r.length || r.length == 0 && pivot == 0);
if (r.length <= 1) return 0;
import std.algorithm : swapAt;
r.swapAt(pivot, 0);
size_t lo = 1, hi = r.length - 1;
loop: for (;;)
{
for (;; ++lo)
{
if (lo > hi) break loop;
if (less(r[0], r[lo])) break;
}
// found the left bound
assert(lo <= hi);
for (;; --hi)
{
if (lo == hi) break loop;
if (less(r[hi], r[0])) break;
}
// found the right bound, swap & make progress
r.swapAt(lo++, hi--);
}
--lo;
r.swapAt(lo, 0);
return lo;
}
