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.
ordered	ordered(1, 1, 2, 3) returns true.
strictlyOrdered	strictlyOrdered(1, 1, 2, 3) returns false.
makeIndex	Creates a separate index for a range.
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 predicate.
partition3	Partitions a range in three parts (less than, equal, greater than the given pivot).
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.
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.
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]).
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.
schwartzSort	Sorts a range using an algorithm akin to the Schwartzian transform, also known as the decorate-sort-undecorate pattern in Python and Lisp. This function is helpful when the sort comparison includes an expensive computation. The complexity is the same as that of the corresponding sort, but schwartzSort evaluates transform only r.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.
sort	Sorts a random-access range according to the predicate less. Performs Ο(r.length * log(r.length)) evaluations of less. Stable sorting requires hasAssignableElements!Range to be true.
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).

Enums

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

Templates

Name	Description
multiSort	void multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less));

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments