Menu
Search

API Documentation

version 2.081.0

overview

View source code
Display the source code in std/algorithm/sorting.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
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. Specifically, permutes elements of r and returns an index k < r.length such that:

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

  • 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[0 .. k] satisfy `!less(e$D( 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 is r.length is 0

Returns

The new position of the 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.

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.