Search
View source code
Display the source code in std/algorithm/sorting.d from which this page was generated on github.
Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# Function `std.algorithm.sorting.pivotPartition`

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

``` size_t pivotPartition(alias less, Range) (   Range r,   size_t pivot ) if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range); ```

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

NameDescription
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

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

## Example

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