std.algorithm.sorting

This is a submodule of std.algorithm. It contains generic sorting algorithms.

Cheat Sheet
Function Name	Description
completeSort	If `a = [10, 20, 30]` and `b = [40, 6, 15]`, then `completeSort(a, b)` leaves `a = [6, 10, 15]` and `b = [20, 30, 40]`. The range `a` must be sorted prior to the call, and as a result the combination `chain(a, b)` is sorted.
isPartitioned	`isPartitioned!"a < 0"([-1, -2, 1, 0, 2])` returns `true` because the predicate is `true` for a portion of the range and `false` afterwards.
isSorted	`isSorted([1, 1, 2, 3])` returns `true`.
isStrictlyMonotonic	`isStrictlyMonotonic([1, 1, 2, 3])` returns `false`.
ordered	`ordered(1, 1, 2, 3)` returns `true`.
strictlyOrdered	`strictlyOrdered(1, 1, 2, 3)` returns `false`.
makeIndex	Creates a separate index for a range.
merge	Lazily merges two or more sorted ranges.
multiSort	Sorts by multiple keys.
nextEvenPermutation	Computes the next lexicographically greater even permutation of a range in-place.
nextPermutation	Computes the next lexicographically greater permutation of a range in-place.
nthPermutation	Computes the nth permutation of a range in-place.
partialSort	If `a = [5, 4, 3, 2, 1]`, then `partialSort(a, 3)` leaves `a[0 .. 3] = [1, 2, 3]`. The other elements of `a` are left in an unspecified order.
partition	Partitions a range according to a unary predicate.
partition3	Partitions a range according to a binary predicate in three parts (less than, equal, greater than the given pivot). Pivot is not given as an index, but instead as an element independent from the range's content.
pivotPartition	Partitions a range according to a binary predicate in two parts: less than or equal, and greater than or equal to the given pivot, passed as an index in the range.
schwartzSort	Sorts with the help of the Schwartzian transform.
sort	Sorts.
topN	Separates the top elements in a range, akin to Quickselect.
topNCopy	Copies out the top elements of a range.
topNIndex	Builds an index of the top elements of a range.

Copyright

Andrei Alexandrescu 2008-.

License

Boost License 1.0.

Authors

Andrei Alexandrescu

Source: std/algorithm/sorting.d

tmpl HeapOps multiSort TimSortImpl validPredicates

alias SortOutput

struct Merge

fn completeSort expandPartition getPivot isPartitioned isSorted isStrictlyMonotonic makeIndex medianOf merge multiSortImpl multiSortPredFun nextEvenPermutation nextPermutation nthPermutation nthPermutationImpl ordered p3 p4 partialSort partition partition3 pivotPartition quickSortImpl schwartzSort shortSort sort sort5 strictlyOrdered topN topNCopy topNImpl topNIndex topNPartition topNPartitionOffMedian trustedMoveEmplace

Types 2

aliasSortOutput = Flag!"sortOutput"

Specifies whether the output of certain algorithm is desired in sorted format.

If set to SortOutput.no, the output should not be sorted.

Otherwise if set to SortOutput.yes, the output should be sorted.

structMerge(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void))

Fields

Rs source

private size_t _lastFrontIndex

private isBidirectional

Methods

@property auto ref front()

private size_t frontIndex()

void popFront()

Constructors

this(Rs source)

Functions 40

void completeSort(alias  less =  "a < b",  SwapStrategy ss =  SwapStrategy.unstable,
         Lhs ,  Rhs)(SortedRange!(Lhs,  less)  lhs,  Rhs rhs) if (hasLength!(Rhs)  &&  hasSlicing!(Rhs)
         &&  hasSwappableElements!Lhs &&  hasSwappableElements!Rhs)

Sorts the random-access range `chain(lhs, rhs)` according to predicate `less`.

fnbool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!(Range))Checks whether a forward range is sorted according to the comparison operation `less`. Performs r.length evaluations of `less`.

fnbool isStrictlyMonotonic(alias less = "a < b", Range)(Range r) if (isForwardRange!Range)ditto

bool ordered(alias  less =  "a < b",  T...)(T values) if ((T.length ==  2 &&  is(typeof(binaryFun!less(values[1],  values[0])) :  bool))
     ||
    (T.length >  2 &&  is(typeof(ordered!less(values[0 ..  1 +  $  /  2])))
         &&  is(typeof(ordered!less(values[$  /  2 ..  $]))))
    )

Like `isSorted`, returns `true` if the given `values` are ordered according to the comparison operation `less`. Unlike `isSorted`, takes values directly instead of structured in a range.

fnbool strictlyOrdered(alias less = "a < b", T...)(T values) if (is(typeof(ordered!less(values))))ditto

Range partition(alias  predicate,  SwapStrategy ss,  Range)(Range r) if (ss ==  SwapStrategy.stable &&  isRandomAccessRange!(Range)  &&  hasLength!Range &&
         hasSlicing!Range &&  hasSwappableElements!Range)

Partitions a range in two using the given `predicate`.

Range partition(alias  predicate,  SwapStrategy ss =  SwapStrategy.unstable,  Range)(Range r) if (ss !=  SwapStrategy.stable &&  isInputRange!Range &&  hasSwappableElements!Range)

ditto

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 https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme.

fnbool isPartitioned(alias pred, Range)(Range r) if (isForwardRange!(Range))Params: pred = The predicate that the range should be partitioned by. r = The range to check. Returns: `true` if `r` is partitioned according to predicate `pred`.

auto partition3(alias  less =  "a < b",  SwapStrategy ss =  SwapStrategy.unstable,  Range,  E)(Range r,  E pivot) if (ss ==  SwapStrategy.unstable &&  isRandomAccessRange!Range
        &&  hasSwappableElements!Range &&  hasLength!Range &&  hasSlicing!Range
        &&  is(typeof(binaryFun!less(r.front,  pivot))  ==  bool)
         &&  is(typeof(binaryFun!less(pivot,  r.front))  ==  bool)
         &&  is(typeof(binaryFun!less(r.front,  r.front))  ==  bool))

Rearranges elements in `r` in three adjacent ranges and returns them.

SortedRange!(RangeIndex, (a,  b)  =>  binaryFun!less(* a,  * b)) makeIndex(
     alias  less =  "a < b",
     SwapStrategy ss =  SwapStrategy.unstable,
     Range,
     RangeIndex)(Range r,  RangeIndex index) if (isForwardRange!(Range)  &&  isRandomAccessRange!(RangeIndex)
     &&  is(ElementType!(RangeIndex) :  ElementType!(Range) *)  &&  hasAssignableElements!RangeIndex)

Computes an index for `r` based on the comparison `less`.

void makeIndex(
     alias  less =  "a < b",
     SwapStrategy ss =  SwapStrategy.unstable,
     Range,
     RangeIndex)(Range r,  RangeIndex index) if (isRandomAccessRange!Range && !isInfinite!Range &&
     isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex &&
     isIntegral!(ElementType!RangeIndex)  &&  hasAssignableElements!RangeIndex)

Ditto

Merge!(less,  Rs) merge(alias  less =  "a < b",  Rs...)(Rs rs) if (Rs.length >=  2 &&
     allSatisfy!(isInputRange,  Rs)  &&
    !is(CommonType!(staticMap!(ElementType,  Rs))  ==  void))

Merge multiple sorted ranges `rs` with less-than predicate function `pred` into one single sorted output range containing the sorted union of the elements of inputs.

private fnbool multiSortPredFun(Range, funs...)(ElementType!Range a, ElementType!Range b)

private fnvoid multiSortImpl(Range, SwapStrategy ss, funs...)(Range r)

private fnsize_t getPivot(alias less, Range)(Range r)

private fnvoid shortSort(alias less, Range)(Range r)

private fnvoid trustedMoveEmplace(T)(ref T source, ref T target) @trusted@trusted wrapper for moveEmplace

private fnvoid sort5(alias lt, Range)(Range r)

fnSortedRange!(Range, less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)Sorts a random-access range according to the predicate `less`.

private fnvoid quickSortImpl(alias less, Range)(Range r, size_t depth)

SortedRange!(R, ((a,  b)  =>  binaryFun!less(unaryFun!transform(a),
                                           unaryFun!transform(b)))) schwartzSort(alias  transform,  alias  less =  "a < b",
         SwapStrategy ss =  SwapStrategy.unstable,  R)(R r) if (isRandomAccessRange!R &&  hasLength!R &&  hasSwappableElements!R &&
    !is(typeof(binaryFun!less)  ==  SwapStrategy))

Alternative sorting method that should be used when comparing keys involves an expensive computation.

auto schwartzSort(alias  transform,  SwapStrategy ss,  R)(R r) if (isRandomAccessRange!R &&  hasLength!R &&  hasSwappableElements!R)

ditto

void partialSort(alias  less =  "a < b",  SwapStrategy ss =  SwapStrategy.unstable,
     Range)(Range r,  size_t n) if (isRandomAccessRange!(Range)  &&  hasLength!(Range)  &&  hasSlicing!(Range))

Reorders the random-access range `r` such that the range `r[0 .. mid]` is the same as if the entire `r` were sorted, and leaves the range `r[mid .. r.length]` in no particular order.

void partialSort(alias  less =  "a < b",  SwapStrategy ss =  SwapStrategy.unstable,
     Range1,  Range2)(Range1 r1,  Range2 r2) if (isRandomAccessRange!(Range1)  &&  hasLength!Range1 &&
     isInputRange!Range2 &&  is(ElementType!Range1 ==  ElementType!Range2)  &&
     hasLvalueElements!Range1 &&  hasLvalueElements!Range2)

Stores the smallest elements of the two ranges in the left-hand range in sorted order.

auto topN(alias  less =  "a < b",
         SwapStrategy ss =  SwapStrategy.unstable,
         Range)(Range r,  size_t nth) if (isRandomAccessRange!(Range)  &&  hasLength!Range &&
     hasSlicing!Range &&  hasAssignableElements!Range)

Reorders the range `r` using swap such that `r[nth]` refers to the element that would fall there if the range were fully sorted.

private fnvoid topNImpl(alias less, R)(R r, size_t n, ref bool useSampling) @trusted

private fnsize_t topNPartition(alias lp, R)(R r, size_t n, bool useSampling)

private fnvoid p3(alias less, Range)(Range r, size_t lo, immutable size_t hi)

private fnvoid p4(alias less, Flag!"leanRight" f, Range)(Range r, size_t lo, immutable size_t hi)

private fnsize_t topNPartitionOffMedian(alias lp, Flag!"leanRight" f, R)(R r, size_t n, bool useSampling)

private fnsize_t expandPartition(alias lp, R)(R r, size_t lo, size_t pivot, size_t hi)

auto topN(alias  less =  "a < b",
         SwapStrategy ss =  SwapStrategy.unstable,
         Range1,  Range2)(Range1 r1,  Range2 r2) if (isRandomAccessRange!(Range1)  &&  hasLength!Range1 &&
     isInputRange!Range2 &&  is(ElementType!Range1 ==  ElementType!Range2)  &&
     hasLvalueElements!Range1 &&  hasLvalueElements!Range2)

Stores the smallest elements of the two ranges in the left-hand range.

TRange topNCopy(alias  less =  "a < b",  SRange,  TRange)(SRange source,  TRange target,  SortOutput sorted =  No.sortOutput) if (isInputRange!(SRange)  &&  isRandomAccessRange!(TRange)
     &&  hasLength!(TRange)  &&  hasSlicing!(TRange))

Copies the top `n` elements of the input range `source` into the random-access range `target`, where `n = target.length`.

void topNIndex(alias  less =  "a < b",  SwapStrategy ss =  SwapStrategy.unstable,
                Range,  RangeIndex)(Range r,  RangeIndex index,  SortOutput sorted =  No.sortOutput) if (isRandomAccessRange!Range &&
     isRandomAccessRange!RangeIndex &&
     hasAssignableElements!RangeIndex)

Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).

private fn

void medianOf(
         alias  less =  "a < b",
         Flag!"leanRight" flag =  No.leanRight,
         Range,
         Indexes...)(Range r,  Indexes i) if (isRandomAccessRange!Range &&  hasLength!Range &&
     Indexes.length >=  2 &&  Indexes.length <=  5 &&
     allSatisfy!(isUnsigned,  Indexes))

bool nextPermutation(alias  less = "a < b",  BidirectionalRange)(BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange &&
     hasSwappableElements!BidirectionalRange)

Permutes `range` in-place to the next lexicographically greater permutation. The predicate `less` defines the lexicographical ordering to be used on the range. If the range is currently the ...

bool nextEvenPermutation(alias  less = "a < b",  BidirectionalRange)(BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange &&
     hasSwappableElements!BidirectionalRange)

Permutes `range` in-place to the next lexicographically greater even permutation. The predicate `less` defines the lexicographical ordering to be used on the range. An even permutation is on...

Range nthPermutation(Range)(auto  ref  Range range,  const  ulong  perm) if (isRandomAccessRange!Range &&  hasLength!Range)

refPermutes `range` into the `perm` permutation.

fnbool nthPermutationImpl(Range)(auto ref Range range, ulong perm) if (isRandomAccessRange!Range && hasLength!Range)Returns: `true` in case the permutation worked, `false` in case `perm` had more digits in the factorial number system than range had elements. This case must not occur as this would lead to out of ...

Templates 4

tmplvalidPredicates(E, less...)

tmplmultiSort(less...)

Sorts a range by multiple keys.

The call multiSort!("a.id < b.id", "a.date > b.date")(r) sorts the range r by id ascending, and sorts elements that have the same id by date descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), but multiSort is faster because it does fewer comparisons (in addition to being more convenient).

Returns

The initial range wrapped as a SortedRange with its predicates

converted to an equivalent single predicate.

Functions

auto multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less) && hasSwappableElements!Range)

tmplHeapOps(alias less, Range)

Functions

void heapSort()(Range r)

void buildHeap()(Range r)

bool isHeap()(Range r)

void siftDown()(Range r, size_t parent, immutable size_t end)

void percolate()(Range r, size_t parent, immutable size_t end)

tmplTimSortImpl(alias pred, R)

Functions

bool greater()(auto ref T a, auto ref T b)

bool greaterEqual()(auto ref T a, auto ref T b)

bool lessEqual()(auto ref T a, auto ref T b)

void sort()(R range, T[] temp)

size_t minRunLength()(size_t n)

size_t firstRun()(R range)

void binaryInsertionSort()(R range, size_t sortedLen = 1)

void mergeAt()(R range, Slice[] stack, immutable size_t at, ref size_t minGallop, ref T[] temp)

void merge()(R range, size_t mid, ref size_t minGallop, ref T[] temp)

T[] ensureCapacity()(size_t minCapacity, T[] temp)

size_t mergeLo()(R range, immutable size_t mid, size_t minGallop, T[] temp)

size_t mergeHi()(R range, immutable size_t mid, size_t minGallop, T[] temp)

void moveEntry(X, Y)(ref X from, const size_t fIdx, ref Y to, const size_t tIdx)

Helper method that moves fromfIdx into totIdx if both are lvalues and uses a plain assignment if not (necessary for backwards compatibility)

Types

struct Slice