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.
Module std.algorithm.sorting
This is a submodule of std
.
It contains generic sorting algorithms.
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 class="pln">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. |
Functions
Name | Description |
---|---|
completeSort(lhs, rhs)
|
Sorts the random-access range chain(lhs, rhs) according to
predicate less .
|
isPartitioned(r)
|
|
isSorted(r)
|
Checks whether a forward range
is sorted according to the comparison operation less . Performs Ο(r )
evaluations of less .
|
isStrictlyMonotonic(r)
|
Checks whether a forward range
is sorted according to the comparison operation less . Performs Ο(r )
evaluations of less .
|
makeIndex(r, index)
|
Computes an index for r based on the comparison less .
|
merge(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(range)
|
Permutes range in-place to the next lexicographically greater even
permutation.
|
nextPermutation(range)
|
Permutes range in-place to the next lexicographically greater
permutation.
|
nthPermutation(range, perm)
|
Permutes range into the perm permutation.
|
nthPermutationImpl(range, perm)
|
|
ordered(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(r, 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 in no particular order.
|
partialSort(r1, r2)
|
Stores the smallest elements of the two ranges in the left-hand range in sorted order. |
partition(r)
|
Partitions a range in two using the given predicate .
|
partition3(r, pivot)
|
Rearranges elements in r in three adjacent ranges and returns
them.
|
pivotPartition(r, pivot)
|
Partitions r around pivot using comparison function less , algorithm akin
to Hoare partition.
|
schwartzSort(r)
|
Alternative sorting method that should be used when comparing keys involves an expensive computation. |
sort(r)
|
Sorts a random-access range according to the predicate less .
|
strictlyOrdered(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(r, 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(r1, r2)
|
Stores the smallest elements of the two ranges in the left-hand range. |
topNCopy(source, target, sorted)
|
Copies the top n elements of the
input range source into the
random-access range target , where n = target .
|
topNIndex(r, index, 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
Name | Description |
---|---|
multiSort
|
Sorts a range by multiple keys. |
Aliases
Name | Type | Description |
---|---|---|
SortOutput
|
Flag!("sortOutput")
|
Specifies whether the output of certain algorithm is desired in sorted format. |
Authors
License
Copyright © 1999-2022 by the D Language Foundation | Page generated by ddox.