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.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 std.range.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.
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 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.length + rhs.length * log(rhs.length)) (best case) to Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) (worst-case) evaluations of swap.
isPartitioned
isSorted Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.
isStrictlyMonotonic Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.
makeIndex 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 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 Permutes range in-place to the next lexicographically greater even permutation.
nextPermutation Permutes range in-place to the next lexicographically greater permutation.
ordered 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 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. Performs Ο(r.length * log(mid)) evaluations of pred. The implementation simply calls topN!(less, ss)(r, n) and then sort!(less, ss)(r[0 .. n]).
partialSort Stores the smallest elements of the two ranges in the left-hand range in sorted order.
partition Partitions a range in two using the given predicate. Specifically, reorders the range r = [left, right) 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 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 Partitions r around pivot using comparison function less, algorithm akin to Hoare partition. Specifically, permutes elements of r and returns an index k < r.length such that:
schwartzSort 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 Sorts a random-access range according to the predicate less. Performs Ο(r.length * log(r.length)) evaluations of less. If less involves expensive computations on the sort key, it may be worthwhile to use schwartzSort instead.
strictlyOrdered 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 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.length] satisfy !less(e2, r[nth]). Effectively, it finds the nth smallest (according to less) elements in r. Performs an expected Ο(r.length) (if unstable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap.
topN Stores the smallest elements of the two ranges in the left-hand range.
topNCopy Copies the top n elements of the input range source into the random-access range target, where n = target.length. Elements of source are not touched. If sorted is true, the target is sorted. Otherwise, the target respects the heap property.
topNIndex 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 auto multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less));

Aliases

Name Type Description
SortOutput std.typecons Specifies whether the output of certain algorithm is desired in sorted format.

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments