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

)

if (

isRandomAccessRange!Range &&

hasLength!Range

hasSlicing!Range

hasAssignableElements!Range

)

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]));

pivotPartition

Parameters

Return Value

Examples

See Also

Meta

Source