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.
pivot using comparison function
less, algorithm akin
to Hoare partition.
size_t pivotPartition(alias less, Range) (
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);
Specifically, permutes elements of
r and returns
k < r such that:
r[pivot]is swapped to
- All elements
r[0 .. k]satisfy
r[k]is greater than or equal to each element to its left according to predicate
- All elements
r[k .. $]satisfy
r[k]is less than or equal to each element to its right according to predicate
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
|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 |
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.
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]));
Copyright © 1999-2023 by the D Language Foundation | Page generated by ddox.