## digitalmars.D - Challenge: fair partition function

• Andrei Alexandrescu (41/41) Feb 08 2016 Consider defining a function that partitions a range around a given
• Xinok (39/53) Feb 08 2016 Ultimately, I think you're going to have to perform two
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```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;
}
```
Feb 08 2016
Xinok <xinok live.com> writes:
```On Monday, 8 February 2016 at 23:25:00 UTC, Andrei Alexandrescu
wrote:
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.

...

Ultimately, I think you're going to have to perform two
comparisons on *some* elements to check for equality. I thought
of a few tricks which may or may not help.

(1) Keep your code as is and add a final pass to count the number
of elements. However, you only need to scan the larger partition
since it contains the index (r.length / 2) and you're trying to
move closer to that point. The elements in the smaller partition
can simply be ignored.

(2) You may have code which looks something like this:

if(less(e, pivot)){ /+ less than +/ }
else if(less(pivot, e)){ /+ greater than +/ }
else{ /+ equal to +/ }}

This is a big win if most of the elements are less than the
pivot, but also a big loss if most of the elements are greater
than the pivot. A simple trick is to repeat the code twice but
swap the order of comparisons so you get:

if(less(pivot, e)){ /+ greater than +/ }
else if(less(e, pivot)){ /+ less than +/ }
else{ /+ equal to +/ }}

This will place us closer to an average 1.5 comparisons per
element which is better than (1).

(3) Similar to (2) except you only compare each element once so
you're not checking for equality. You're simply alternating
between checking if (e < pivot) or if (pivot < e). So the code
may look something like this:

if(less(pivot, e)){ less }
else{ greater or equal }

if(less(e, pivot)){ greater }
else{ less or equal }

From this, you can group the elements into four partitions:

[LE L G GE]

So you have elements which are definitely less than or greater
than the pivot but also some elements which *may* be equal to the
pivot. Combine this with the first trick (1) and you only have to
scan LE or GE for equality but not both. This is putting us
closer to an average 1.25 comparisons per element but a 4-way
partition would also require much more work.
```
Feb 08 2016