Report a bug
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 a local clone.

# mir.ndslice.sorting

This is a submodule of mir.ndslice.

Note The combination of pairwise  with lambda "a <= b" ("a < b") and all  can be used to check if an ndslice is sorted (strictly monotonic). iota  can be used to make an index. map  and zip  can be used to create Schwartzian transform. See also the examples in the module.

flattened
isSorted and isStrictlyMonotonic
Authors:
Andrei Alexandrescu (Phobos), Ilya Yaroshenko (API, rework, Mir adoptation)
Examples:
Check if ndslice is sorted, or strictly monotonic.
```import mir.algorithm.iteration: all;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: pairwise;

auto arr = [1, 1, 2].sliced;

assert(arr.pairwise!"a <= b".all);
assert(!arr.pairwise!"a < b".all);

arr = [4, 3, 2, 1].sliced;

assert(!arr.pairwise!"a <= b".all);
assert(!arr.pairwise!"a < b".all);

sort(arr);

assert(arr.pairwise!"a <= b".all);
assert(arr.pairwise!"a < b".all);
```
Examples:
Create index
```import mir.algorithm.iteration: all;
import mir.ndslice.allocation: slice;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: iota, pairwise;

auto arr = [4, 2, 3, 1].sliced;

auto index = arr.length.iota.slice;
index.sort!((a, b) => arr[a] < arr[b]);

assert(arr[index].pairwise!"a <= b".all);
```
Examples:
Schwartzian transform
```import mir.algorithm.iteration: all;
import mir.ndslice.allocation: slice;
import mir.ndslice.slice: sliced;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: zip, map, pairwise;

alias transform = (a) => (a - 3) ^^ 2;

auto arr = [4, 2, 3, 1].sliced;

arr.map!transform.slice.zip(arr).sort!((l, r) => l.a < r.a);

assert(arr.map!transform.pairwise!"a <= b".all);
```
template `sort`(alias less = "a < b")
Sorts ndslice, array, or series.
Examples:
```import mir.algorithm.iteration: all;
import mir.ndslice.slice;
import mir.ndslice.sorting: sort;
import mir.ndslice.topology: pairwise;

int arr = [7,1,3,2,9,0,5,4,8,6];

auto data = arr[].sliced(arr.length);
data.sort();
assert(data.pairwise!"a <= b".all);
```
Examples:
one-dimensional series
```import mir.series;

auto index = [4, 2, 1, 3, 0].sliced;
auto data = [5.6, 3.4, 2.1, 7.8, 0.1].sliced;
auto series = index.series(data);
series.sort;
assert(series.index == [0, 1, 2, 3, 4]);
assert(series.data == [0.1, 2.1, 3.4, 7.8, 5.6]);
/// initial index and data are the same
assert(index.iterator is series.index.iterator);
assert(data.iterator is series.data.iterator);

foreach(obs; series)
{
static assert(is(typeof(obs) == Observation!(int, double)));
}
```
Examples:
two-dimensional series
```import mir.series;
import mir.ndslice.allocation: uninitSlice;

auto index = [4, 2, 3, 1].sliced;
auto data =
[2.1, 3.4,
5.6, 7.8,
3.9, 9.0,
4.0, 2.0].sliced(4, 2);
auto series = index.series(data);

series.sort(
uninitSlice!size_t(series.length), // index buffer
uninitSlice!double(series.length), // data buffer
);

assert(series.index == [1, 2, 3, 4]);
assert(series.data ==
[[4.0, 2.0],
[5.6, 7.8],
[3.9, 9.0],
[2.1, 3.4]]);
/// initial index and data are the same
assert(index.iterator is series.index.iterator);
assert(data.iterator is series.data.iterator);
```
Slice!(Iterator, N, kind) `sort`(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) `slice`);
Sort n-dimensional slice.
T[] `sort`(T)(T[] `ar`);
Sort for arrays
Series!(IndexIterator, Iterator, N, kind) `sort`(IndexIterator, Iterator, size_t N, SliceKind kind)(Series!(IndexIterator, Iterator, N, kind) `series`)
if (N == 1);
Sort for one-dimensional Series.
Series!(IndexIterator, Iterator, N, kind) `sort`(IndexIterator, Iterator, size_t N, SliceKind kind, SortIndexIterator, DataIterator)(Series!(IndexIterator, Iterator, N, kind) `series`, Slice!SortIndexIterator `indexBuffer`, Slice!DataIterator `dataBuffer`);
Sort for n-dimensional Series.
template `assumeSortedContains`(alias test = "a < b")
Returns:
true if a sorted array contains the value.
Parameters:
 test strict ordering symmetric predicate For non-symmetric predicates please use a structure with two opCalls or an alias of two global functions, that correponds to (array[i], value) and (value, array[i]) cases.
bool `assumeSortedContains`(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) `slice`, auto ref scope const V `v`);

bool `assumeSortedContains`(T, V)(scope T[] `ar`, auto ref scope const V `v`);
Parameters:
 Slice!(Iterator, 1, kind) `slice` sorted one-dimensional slice or array. V `v` value to test with. It is passed to second argument.
template `assumeSortedEqualIndex`(alias test = "a < b")
Returns:
the smallest index of a sorted array such that the index corresponds to the arrays element at the index according to the predicate and -1 if the array doesn't contain corresponding element.
Parameters:
 test strict ordering symmetric predicate. For non-symmetric predicates please use a structure with two opCalls or an alias of two global functions, that correponds to (array[i], value) and (value, array[i]) cases.
Examples:
```// sorted: a < b
auto a = [0, 1, 2, 3, 4, 6];

assert(a.assumeSortedEqualIndex(2) == 2);
assert(a.assumeSortedEqualIndex(5) == -1);

// <= non strict predicates doesn't work
assert(a.assumeSortedEqualIndex!"a <= b"(2) == -1);
```
sizediff_t `assumeSortedEqualIndex`(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) `slice`, auto ref scope const V `v`);

sizediff_t `assumeSortedEqualIndex`(T, V)(scope T[] `ar`, auto ref scope const V `v`);
Parameters:
 Slice!(Iterator, 1, kind) `slice` sorted one-dimensional slice or array. V `v` value to test with. It is passed to second argument.
template `transitionIndex`(alias test = "a < b")
Computes transition index using binary search. It is low-level API for lower and upper bounds of a sorted array.
Parameters:
 test ordering predicate for ((array[i], value)) pairs.
Examples:
```// sorted: a < b
auto a = [0, 1, 2, 3, 4, 6];

auto i = a.transitionIndex(2);
assert(i == 2);
auto lowerBound = a[0 .. i];

auto j = a.transitionIndex!"a <= b"(2);
assert(j == 3);
auto upperBound = a[j .. \$];

assert(a.transitionIndex(a[\$ - 1]) == a.length - 1);
assert(a.transitionIndex!"a <= b"(a[\$ - 1]) == a.length);
```
size_t `transitionIndex`(Iterator, SliceKind kind, V)(auto ref Slice!(Iterator, 1, kind) `slice`, auto ref scope const V `v`);

size_t `transitionIndex`(T, V)(scope T[] `ar`, auto ref scope const V `v`);
Parameters:
 Slice!(Iterator, 1, kind) `slice` sorted one-dimensional slice or array. V `v` value to test with. It is passed to second argument.
Slice!(I*) `makeIndex`(I = size_t, alias less = "a < b", Iterator, SliceKind kind)(Slice!(Iterator, 1, kind) `r`);
Computes an index for `r` based on the comparison less. The index is a sorted array of 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 indices, 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.
Can be combined with indexed  to create a view that is sorted based on the index.
Parameters:
 less The comparison to use. Slice!(Iterator, 1, kind) `r` The slice/array to index.
Returns:
Index slice/array.
I[] `makeIndex`(I = size_t, alias less = "a < b", T)(scope T[] `r`);
Examples:
```import mir.algorithm.iteration: all;
import mir.ndslice.topology: indexed, pairwise;

immutable arr = [ 2, 3, 1, 5, 0 ];
auto index = arr.makeIndex;

assert(arr.indexed(index).pairwise!"a < b".all);
```
Examples:
Sort based on index created from a separate array
```import mir.algorithm.iteration: equal;
import mir.ndslice.topology: indexed;

immutable arr0 = [ 2, 3, 1, 5,  0 ];
immutable arr1 = [ 1, 5, 4, 2, -1 ];

auto index = makeIndex(arr0);
assert(index.equal([4, 2, 0, 1, 3]));
auto view = arr1.indexed(index);
assert(view.equal([-1, 4, 1, 5, 2]));
```
template `pivotPartition`(alias less = "a < b")
Partitions slice around pivot using comparison function less, algorithm akin to Hoare partition. Specifically, permutes elements of slice and returns an index k < slice.length such that:
• slice[pivot] is swapped to slice[k]
• All elements e in subrange slice[0 .. k] satisfy !less(slice[k], e) (i.e. slice[k] is greater than or equal to each element to its left according to predicate less)
• All elements e in subrange slice[k .. \$] satisfy !less(e, slice[k]) (i.e. slice[k] is less than or equal to each element to its right according to predicate less)
If slice contains equivalent elements, multiple permutations of slice may satisfy these constraints. In such cases, `pivotPartition` attempts to distribute equivalent elements fairly to the left and right of k such that k stays close to slice.length / 2.
Parameters:
 less The predicate used for comparison
Returns:
The new position of the pivot
Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.
Examples:
pivotPartition with 1-dimensional Slice
```import mir.ndslice.slice: sliced;
import mir.algorithm.iteration: all;

auto x = [5, 3, 2, 6, 4, 1, 3, 7].sliced;
size_t pivot = pivotPartition(x, x.length / 2);

assert(x[0 .. pivot].all!(a => a <= x[pivot]));
assert(x[pivot .. \$].all!(a => a >= x[pivot]));
```
Examples:
pivotPartition with 2-dimensional Slice
```import mir.ndslice.fuse: fuse;
import mir.ndslice.topology: flattened;
import mir.algorithm.iteration: all;

auto x = [
[5, 3, 2, 6],
[4, 1, 3, 7]
].fuse;

size_t pivot = pivotPartition(x, x.elementCount / 2);

auto xFlattened = x.flattened;
assert(xFlattened[0 .. pivot].all!(a => a <= xFlattened[pivot]));
assert(xFlattened[pivot .. \$].all!(a => a >= xFlattened[pivot]));
```
size_t `pivotPartition`(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) `slice`, size_t `pivot`);
Parameters:
 Slice!(Iterator, N, kind) `slice` slice being partitioned size_t `pivot` The index of the pivot for partitioning, must be less than `slice`.length or 0 if `slice`.length is 0
template `partitionAt`(alias less = "a < b")
Partitions slice, such that all elements e1 from slice to slice[nth] satisfy !less(slice[nth], e1), and all elements e2 from slice[nth] to slice[slice.length] satisfy !less(e2, slice[nth]). This effectively reorders slice such that slice[nth] refers to the element that would fall there if the range were fully sorted. Performs an expected Ο(slice.length) evaluations of less and swap, with a worst case of Ο(slice.length^^2).
This function implements the Fast, Deterministic Selection algorithm that is implemented in the topN function in D's standard library (as of version 2.092.0).
Parameters:
 less The predicate to sort by.
Examples:
Partition 1-dimensional slice at nth
```import mir.ndslice.slice: sliced;

size_t nth = 2;
auto x = [3, 1, 5, 2, 0].sliced;
x.partitionAt(nth);
assert(x[nth] == 2);
```
Examples:
Partition 2-dimensional slice
```import mir.ndslice.slice: sliced;

size_t nth = 4;
auto x = [3, 1, 5, 2, 0, 7].sliced(3, 2);
x.partitionAt(nth);
assert(x[2, 0] == 5);
```
Examples:
Can supply alternate ordering function
```import mir.ndslice.slice: sliced;

size_t nth = 2;
auto x = [3, 1, 5, 2, 0].sliced;
x.partitionAt!("a > b")(nth);
assert(x[nth] == 2);
```
nothrow @nogc @trusted void `partitionAt`(Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) `slice`, size_t `nth`);
Parameters:
 Slice!(Iterator, N, kind) `slice` n-dimensional slice size_t `nth` The index of the element that should be in sorted position after the function is finished.