std.algorithm.sorting

enum SortOutput: int;

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

no

Don't sort output

yes

Sort output

void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(SortedRange!(Range1, less) lhs, Range2 rhs) if (hasLength!Range2 && hasSlicing!Range2);

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.

Examples:

import std.range : assumeSorted;
int[] a = [ 1, 2, 3 ];
int[] b = [ 4, 0, 6, 5 ];
completeSort(assumeSorted(a), b);
assert(a == [ 0, 1, 2 ]);
assert(b == [ 3, 4, 5, 6 ]);

bool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!Range);

Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.

Examples:

int[] arr = [4, 3, 2, 1];
assert(!isSorted(arr));
sort(arr);
assert(isSorted(arr));
sort!("a > b")(arr);
assert(isSorted!("a > b")(arr));

bool ordered(alias less = "a < b", T...)(T values) if (T.length == 2 && is(typeof(binaryFun!less(values[1], values[0])) : bool) || T.length > 2 && is(typeof(ordered!less(values[0..1 + $ / 2]))) && is(typeof(ordered!less(values[$ / 2..$]))));

bool strictlyOrdered(alias less = "a < b", T...)(T values) if (is(typeof(ordered!less(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.

ordered allows repeated values, e.g. ordered(1, 1, 2) is true. To verify that the values are ordered strictly monotonically, use strictlyOrdered; strictlyOrdered(1, 1, 2) is false.

With either function, the predicate must be a strict ordering just like with isSorted. For example, using "a <= b" instead of "a < b" is incorrect and will cause failed assertions.

Parameters:

T values	The tested value
less	The comparison predicate

Returns:

true if the values are ordered; ordered allows for duplicates, strictlyOrdered does not.

Examples:

assert(ordered(42, 42, 43));
assert(!strictlyOrdered(43, 42, 45));
assert(ordered(42, 42, 43));
assert(!strictlyOrdered(42, 42, 43));
assert(!ordered(43, 42, 45));
// Ordered lexicographically
assert(ordered("Jane", "Jim", "Joe"));
assert(strictlyOrdered("Jane", "Jim", "Joe"));
// Incidentally also ordered by length decreasing
assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
// ... but not strictly so: "Jim" and "Joe" have the same length
assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));

Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if (ss == SwapStrategy.stable && isRandomAccessRange!Range || ss != SwapStrategy.stable && isForwardRange!Range);

Partitions a range in two using pred as a predicate. Specifically, reorders the range r = [left, right) using swap such that all elements i for which pred(i) is true come before all elements j for which pred(j) returns false.

Performs Ο(r.length) (if unstable or semistable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).

Returns:

The right part of r after partitioning.

If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which pred(a) == pred(b). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements a, b in the left part of r for which pred(a) == pred(b).

See Also:

STL's partition
STL's stable_partition

Examples:

import std.algorithm : count, find; // FIXME
import std.conv : text;

auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// Partition arr such that even numbers come first
auto r = partition!(even)(arr);
// Now arr is separated in evens and odds.
// Numbers may have become shuffled due to instability
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);

// Can also specify the predicate as a string.
// Use 'a' as the predicate argument name
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);

// Now for a stable partition:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// In case the predicate needs to hold its own state, use a delegate:
arr[] = Arr[];
int x = 3;
// Put stuff greater than 3 on the left
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);

bool isPartitioned(alias pred, Range)(Range r) if (isForwardRange!Range);

Returns true if r is partitioned according to predicate pred.

Examples:

int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
assert(isPartitioned!"a & 1"(r));

auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Range r, E pivot) if (ss == SwapStrategy.unstable && isRandomAccessRange!Range && hasSwappableElements!Range && hasLength!Range && is(typeof(binaryFun!less(r.front, pivot)) == bool) && is(typeof(binaryFun!less(pivot, r.front)) == bool) && is(typeof(binaryFun!less(r.front, r.front)) == bool));

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.

Bugs:

stable partition3 has not been implemented yet.

Examples:

auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
auto pieces = partition3(a, 4);
assert(pieces[0] == [ 1, 3 ]);
assert(pieces[1] == [ 4, 4, 4 ]);
assert(pieces[2] == [ 8, 7 ]);

SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*));
void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex));

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.

The first overload of makeIndex writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range to be a forward range, and the latter requires it to be a random-access range.

makeIndex overwrites its second argument with the result, but never reallocates it.

Returns:

The pointer-based version returns a SortedRange wrapper over index, of type SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) thus reflecting the ordering of the index. The index-based version returns void because the ordering relation involves not only index but also r.

Throws:

If the second argument's length is less than that of the range indexed, an exception is thrown.

Examples:

immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// index using pointers
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// index using offsets
auto index2 = new size_t[arr.length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
    ((size_t a, size_t b){ return arr[a] < arr[b];})
    (index2));

template multiSort(less...)

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

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).

Examples:

static struct Point { int x, y; }
auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ];
auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ];
multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
assert(pts1 == pts2);

SortedRange!(Range, less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if ((ss == SwapStrategy.unstable && (hasSwappableElements!Range || hasAssignableElements!Range) || ss != SwapStrategy.unstable && hasAssignableElements!Range) && isRandomAccessRange!Range && hasSlicing!Range && hasLength!Range);

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.

sort returns a std.range.SortedRange over the original range, which functions that can take advantage of sorted data can then use to know that the range is sorted and adjust accordingly. The std.range.SortedRange is a wrapper around the original range, so both it and the original range are sorted, but other functions won't know that the original range has been sorted, whereas they can know that std.range.SortedRange has been sorted.

The predicate is expected to satisfy certain rules in order for sort to behave as expected - otherwise, the program may fail on certain inputs (but not others) when not compiled in release mode, due to the cursory assumeSorted check. Specifically, sort expects less(a,b) && less(b,c) to imply less(a,c) (transitivity), and, conversely, !less(a,b) && !less(b,c) to imply !less(a,c). Note that the default predicate ("a < b") does not always satisfy these conditions for floating point types, because the expression will always be false when either a or b is NaN.

Returns:

The initial range wrapped as a SortedRange with the predicate binaryFun!less.

Algorithms: en.wikipedia.org/wiki/Introsort is used for unstable sorting and Timsort is used for stable sorting. Each algorithm has benefits beyond stability. Introsort is generally faster but Timsort may achieve greater speeds on data with low entropy or if predicate calls are expensive. Introsort performs no allocations whereas Timsort will perform one or more allocations per call. Both algorithms have Ο(n log n) worst-case time complexity.

See Also:

std.range.assumeSorted
std.range.SortedRange
std.algorithm.mutation.SwapStrategy
std.functional.binaryFun

Examples:

int[] array = [ 1, 2, 3, 4 ];
// sort in descending order
sort!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);
// sort in ascending order
sort(array);
assert(array == [ 1, 2, 3, 4 ]);
// sort with a delegate
bool myComp(int x, int y) @safe pure nothrow { return x > y; }
sort!(myComp)(array);
assert(array == [ 4, 3, 2, 1 ]);

Examples:

// Showcase stable sorting
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);

SortedRange!(R, (a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b))) schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(R r) if (isRandomAccessRange!R && hasLength!R);

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.

Examples:

uint hashFun(string) { ... expensive computation ... }
string[] array = ...;
// Sort strings by hash, slow
sort!((a, b) => hashFun(a) < hashFun(b))(array);
// Sort strings by hash, fast (only computes arr.length hashes):
schwartzSort!(hashFun, "a < b")(array);

The schwartzSort function might require less temporary data and be faster than the Perl idiom or the decorate-sort-undecorate idiom present in Python and Lisp. This is because sorting is done in-place and only minimal extra data (one array of transformed elements) is created.

To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted is not provided because the effect can be achieved by calling isSorted!less(map!transform(r)).

Returns:

The initial range wrapped as a SortedRange with the predicate (a, b) => binaryFun!less(transform(a), transform(b)).

void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t n) if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);

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]).

Examples:

int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
partialSort(a, 5);
assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);

void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth) if (isRandomAccessRange!Range && hasLength!Range);

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.

If n >= r.length, the algorithm has no effect.

See Also:

topNIndex, STL's nth_element

Bugs:

Stable topN has not been implemented yet.

Examples:

int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
auto n = 4;
topN!"a < b"(v, n);
assert(v[n] == 9);

void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 r1, Range2 r2) if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2));

Stores the smallest elements of the two ranges in the left-hand range.

Examples:

int[] a = [ 5, 7, 2, 6, 7 ];
int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
topN(a, b);
sort(a);
assert(a == [0, 1, 2, 2, 3]);

TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = SortOutput.no) if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);

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.

Examples:

int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
int[] b = new int[3];
topNCopy(a, b, SortOutput.yes);
assert(b == [ 0, 1, 2 ]);

void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index, SortOutput sorted = SortOutput.no) if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex && isIntegral!(ElementType!RangeIndex));
void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index, SortOutput sorted = SortOutput.no) if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex && is(ElementType!RangeIndex == ElementType!Range*));

Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).

Similar to topN, except that the range is not modified.

Parameters:

less	A binary predicate that defines the ordering of range elements. Defaults to a < b.
ss	(Not implemented yet.) Specify the swapping strategy.
Range r	A random-access range of elements to make an index for.
RangeIndex index	A random-access range with assignable elements to build the index in. The length of this range determines how many top elements to index in r. This index range can either have integral elements, in which case the constructed index will consist of zero-based numerical indices into r; or it can have pointers to the element type of r, in which case the constructed index will be pointers to the top elements in r.
SortOutput sorted	Determines whether to sort the index by the elements they refer to.

See Also:

topN, topNCopy.

Bugs:

The swapping strategy parameter is not implemented yet; currently it is ignored.

Examples:

// Construct index to top 3 elements using numerical indices:
int[] a = [ 10, 2, 7, 5, 8, 1 ];
int[] index = new int[3];
topNIndex(a, index, SortOutput.yes);
assert(index == [5, 1, 3]); // because a[5]==1, a[1]==2, a[3]==5

// Construct index to top 3 elements using pointer indices:
int*[] ptrIndex = new int*[3];
topNIndex(a, ptrIndex, SortOutput.yes);
assert(ptrIndex == [ &a[5], &a[1], &a[3] ]);

bool nextPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);

Permutes range in-place to the next lexicographically greater permutation.

The predicate less defines the lexicographical ordering to be used on the range.

If the range is currently the lexicographically greatest permutation, it is permuted back to the least permutation and false is returned. Otherwise, true is returned. One can thus generate all permutations of a range by sorting it according to less, which produces the lexicographically least permutation, and then calling nextPermutation until it returns false. This is guaranteed to generate all distinct permutations of the range exactly once. If there are N elements in the range and all of them are unique, then N! permutations will be generated. Otherwise, if there are some duplicated elements, fewer permutations will be produced.

// Enumerate all permutations
int[] a = [1,2,3,4,5];
do
{
    // use the current permutation and
    // proceed to the next permutation of the array.
} while (nextPermutation(a));

Returns:

false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.

Examples:

// Step through all permutations of a sorted array in lexicographic order
int[] a = [1,2,3];
assert(nextPermutation(a) == true);
assert(a == [1,3,2]);
assert(nextPermutation(a) == true);
assert(a == [2,1,3]);
assert(nextPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextPermutation(a) == true);
assert(a == [3,2,1]);
assert(nextPermutation(a) == false);
assert(a == [1,2,3]);

Examples:

// Step through permutations of an array containing duplicate elements:
int[] a = [1,1,2];
assert(nextPermutation(a) == true);
assert(a == [1,2,1]);
assert(nextPermutation(a) == true);
assert(a == [2,1,1]);
assert(nextPermutation(a) == false);
assert(a == [1,1,2]);

bool nextEvenPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);

Permutes range in-place to the next lexicographically greater even permutation.

The predicate less defines the lexicographical ordering to be used on the range.

An even permutation is one which is produced by swapping an even number of pairs of elements in the original range. The set of even permutations is distinct from the set of all permutations only when there are no duplicate elements in the range. If the range has N unique elements, then there are exactly N!/2 even permutations.

If the range is already the lexicographically greatest even permutation, it is permuted back to the least even permutation and false is returned. Otherwise, true is returned, and the range is modified in-place to be the lexicographically next even permutation.

One can thus generate the even permutations of a range with unique elements by starting with the lexicographically smallest permutation, and repeatedly calling nextEvenPermutation until it returns false.

// Enumerate even permutations
int[] a = [1,2,3,4,5];
do
{
    // use the current permutation and
    // proceed to the next even permutation of the array.
} while (nextEvenPermutation(a));

One can also generate the odd permutations of a range by noting that permutations obey the rule that even + even = even, and odd + even = odd. Thus, by swapping the last two elements of a lexicographically least range, it is turned into the first odd permutation. Then calling nextEvenPermutation on this first odd permutation will generate the next even permutation relative to this odd permutation, which is actually the next odd permutation of the original range. Thus, by repeatedly calling nextEvenPermutation until it returns false, one enumerates the odd permutations of the original range.

// Enumerate odd permutations
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]);    // a is now the first odd permutation of [1,2,3,4,5]
do
{
    // use the current permutation and
    // proceed to the next odd permutation of the original array
    // (which is an even permutation of the first odd permutation).
} while (nextEvenPermutation(a));

Warning: Since even permutations are only distinct from all permutations when the range elements are unique, this function assumes that there are no duplicate elements under the specified ordering. If this is not true, some permutations may fail to be generated. When the range has non-unique elements, you should use nextPermutation  instead.

Returns:

false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.

Examples:

// Step through even permutations of a sorted array in lexicographic order
int[] a = [1,2,3];
assert(nextEvenPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextEvenPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextEvenPermutation(a) == false);
assert(a == [1,2,3]);

Examples:

Even permutations are useful for generating coordinates of certain geometric shapes. Here's a non-trivial example:

import std.math : sqrt;

// Print the 60 vertices of a uniform truncated icosahedron (soccer ball)
enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Golden ratio
real[][] seeds = [
    [0.0, 1.0, 3.0*Phi],
    [1.0, 2.0+Phi, 2.0*Phi],
    [Phi, 2.0, Phi^^3]
];
size_t n;
foreach (seed; seeds)
{
    // Loop over even permutations of each seed
    do
    {
        // Loop over all sign changes of each permutation
        size_t i;
        do
        {
            // Generate all possible sign changes
            for (i=0; i < seed.length; i++)
            {
                if (seed[i] != 0.0)
                {
                    seed[i] = -seed[i];
                    if (seed[i] < 0.0)
                        break;
                }
            }
            n++;
        } while (i < seed.length);
    } while (nextEvenPermutation(seed));
}
assert(n == 60);