The OpenD Programming Language

pivotPartition

Partitions r around pivot using comparison function less, algorithm akin to Hoare partition.

Specifically, permutes elements of r and returns an index k < r.length such that:

  • r[pivot] is swapped to r[k]
  • All elements e in subrange r[0 .. k] satisfy !less(r[k], e) (i.e. r[k] is greater than or equal to each element to its left according to predicate less)
  • All elements e in subrange r[k .. $] satisfy !less(e, r[k]) (i.e. r[k] is less than or equal to each element to its right according to predicate less)

If r contains equivalent elements, multiple permutations of r satisfy these constraints. In such cases, pivotPartition attempts to distribute equivalent elements fairly to the left and right of k such that k stays close to r.length / 2.

size_t
pivotPartition
(
alias less = "a < b"
Range
)
(
Range r
,
size_t pivot
)

Parameters

less

The predicate used for comparison, modeled as a strict weak ordering (irreflexive, antisymmetric, transitive, and implying a transitive equivalence)

r Range

The range being partitioned

pivot size_t

The index of the pivot for partitioning, must be less than r.length or 0 if r.length is 0

Return Value

Type: size_t

The new position of the pivot

Examples

int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
size_t pivot = pivotPartition(a, a.length / 2);
import std.algorithm.searching : all;
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));

See Also

Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.

Meta