pivotPartition

size_t pivotPartition(alias  less =  "a < b",  Range)(Range r,  size_t pivot) if (isRandomAccessRange!Range &&  hasLength!Range &&  hasSlicing!Range &&  hasAssignableElements!Range)

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.

Parameters

`less`	The predicate used for comparison, modeled as a strict weak ordering (irreflexive, antisymmetric, transitive, and implying a transitive equivalence)
`r`	The range being partitioned
`pivot`	The index of the pivot for partitioning, must be less than `r.length` or `0` if `r.length` is `0`

Returns

The new position of the pivot

pivotPartition

Parameters

Returns

See Also