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. |
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. |
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 . The left-hand side of the range lhs is
assumed to be already sorted; rhs is assumed to be unsorted. The
exact strategy chosen depends on the relative sizes of lhs and
rhs . Performs Ο(lhs )
(best case) to Ο((lhs ) (worst-case) evaluations of swap .
|
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 . The
index is a sorted array of pointers or indices into the original
range. This technique is similar to sorting, but it is more flexible
because (1) it allows "sorting" of immutable collections, (2) allows
binary search even if the original collection does not offer random
access, (3) allows multiple indexes, each on a different predicate,
and (4) may be faster when dealing with large objects. However, using
an index may also be slower under certain circumstances due to the
extra indirection, and is always larger than a sorting-based solution
because it needs space for the index in addition to the original
collection. The complexity is the same as sort 's.
|
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. Duplicates are not eliminated, meaning that the total
number of elements in the output is the sum of all elements in the ranges
passed to it; the length member is offered if all inputs also have
length . The element types of all the inputs must have a common type
CommonType .
|
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.
|
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. Performs
Ο(r ) evaluations of pred . The
implementation simply calls topN!(less, ss)(r, n) and then sort!(less, ss)(r[0 .. n]) .
|
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 .
Specifically, reorders the range r = [left, rightclass="pln">RPAREN using swap
such that all elements i for which predicate(i) is true come
before all elements j for which predicate(j) returns false .
|
partition3(r, pivot)
|
Rearranges elements in r in three adjacent ranges and returns
them. The first and leftmost range only contains elements in r
less than pivot . The second and middle range only contains
elements in r that are equal to pivot . Finally, the third
and rightmost range only contains elements in r that are greater
than pivot . The less-than test is defined by the binary function
less .
|
pivotPartition(r, pivot)
|
Partitions r around pivot using comparison function less , algorithm akin
to Hoare partition. Specifically, permutes elements of r and returns
an index k < r such that:
|
schwartzSort(r)
|
Alternative sorting method that should be used when comparing keys involves an
expensive computation. Instead of using less(a, b) for comparing elements,
schwartzSort uses less(transform(a), transform(b)) . The values of the
transform function are precomputed in a temporary array, thus saving on
repeatedly computing it. Conversely, if the cost of transform is small
compared to the cost of allocating and filling the precomputed array, sort
may be faster and therefore preferable.
|
sort(r)
|
Sorts a random-access range according to the predicate less . Performs
Ο(r ) evaluations of less . If less involves
expensive computations on the sort key, it may be worthwhile to use
schwartzSort instead.
|
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. In addition, it also partitions r such that all elements
e1 from r[0] to r[nth] satisfy !less(r[nth], e1) ,
and all elements e2 from r[nth] to r[r satisfy
!less(e2, r[nth]) . Effectively, it finds the nth smallest
(according to less ) elements in r . Performs an expected
Ο(r ) (if unstable) or Ο(r )
(if stable) evaluations of less and swap .
|
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 .
Elements of source are not touched. If sorted is true , the target is sorted. Otherwise, the target
respects the heap property.
|
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. 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).
|
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.