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 `$(REF chain, std,range)(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.

Members

Aliases

SortOutput alias SortOutput = Flag!"sortOutput": Specifies whether the output of certain algorithm is desired in sorted format.

Functions

completeSort void completeSort(SortedRange!(Lhs, less) lhs, Rhs rhs): Sorts the random-access range chain(lhs, rhs) according to predicate less.
isPartitioned bool isPartitioned(Range r)
isSorted bool isSorted(Range r)
isStrictlyMonotonic bool isStrictlyMonotonic(Range r): Checks whether a forward range is sorted according to the comparison operation less. Performs O(r.length) evaluations of less.
makeIndex SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) makeIndex(Range r, RangeIndex index)
void makeIndex(Range r, RangeIndex index): Computes an index for r based on the comparison less.
merge Merge!(less, Rs) merge(Rs rs): 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.
nextEvenPermutation bool nextEvenPermutation(BidirectionalRange range): Permutes range in-place to the next lexicographically greater even permutation.
nextPermutation bool nextPermutation(BidirectionalRange range): Permutes range in-place to the next lexicographically greater permutation.
nthPermutation Range nthPermutation(Range range, ulong perm): Permutes range into the perm permutation.
nthPermutationImpl bool nthPermutationImpl(Range range, ulong perm)
ordered bool ordered(T values): 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.
partialSort void partialSort(Range r, size_t n): 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.
partialSort void partialSort(Range1 r1, Range2 r2): Stores the smallest elements of the two ranges in the left-hand range in sorted order.
partition Range partition(Range r): Partitions a range in two using the given predicate.
partition3 auto partition3(Range r, E pivot): Rearranges elements in r in three adjacent ranges and returns them.
pivotPartition size_t pivotPartition(Range r, size_t pivot): Partitions r around pivot using comparison function less, algorithm akin to Hoare partition.
schwartzSort SortedRange!(R, ((a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b)))) schwartzSort(R r)
auto schwartzSort(R r): Alternative sorting method that should be used when comparing keys involves an expensive computation.
sort SortedRange!(Range, less) sort(Range r): Sorts a random-access range according to the predicate less.
strictlyOrdered bool strictlyOrdered(T values): 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.
topN auto topN(Range r, size_t nth): Reorders the range r using swap such that r[nth] refers to the element that would fall there if the range were fully sorted.
topN auto topN(Range1 r1, Range2 r2): Stores the smallest elements of the two ranges in the left-hand range.
topNCopy TRange topNCopy(SRange source, TRange target, SortOutput sorted): Copies the top n elements of the input range source into the random-access range target, where n = target.length.
topNIndex void topNIndex(Range r, RangeIndex index, SortOutput sorted): Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).

Templates

multiSort template multiSort(less...): Sorts a range by multiple keys.

std.algorithm.sorting

Members

Aliases

Functions

Templates

Meta

Source

License

Copyright

Authors