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.

Members

Functions

makeIndex Slice!(I*) makeIndex(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.
makeIndex I[] makeIndex(T[] r)
medianOf void medianOf(Iterator a, Iterator b): Undocumented in source. Be warned that the author may not have intended to support it.
medianOf void medianOf(Iterator a, Iterator b, Iterator c): Undocumented in source. Be warned that the author may not have intended to support it.
medianOf void medianOf(Iterator a, Iterator b, Iterator c, Iterator d): Undocumented in source. Be warned that the author may not have intended to support it.
medianOf void medianOf(Iterator a, Iterator b, Iterator c, Iterator d, Iterator e): Undocumented in source. Be warned that the author may not have intended to support it.
quickSortImpl void quickSortImpl(Slice!Iterator slice): initial index and data are the same
setPivot void setPivot(size_t length, Iterator l, Iterator mid, Iterator r): Undocumented in source. Be warned that the author may not have intended to support it.

Templates

assumeSortedContains template assumeSortedContains(alias test = "a < b")
assumeSortedEqualIndex template assumeSortedEqualIndex(alias test = "a < b")
checkPartitionAtAll template checkPartitionAtAll(alias less = "a < b"): Undocumented in source.
partitionAt template partitionAt(alias less = "a < b"): Partitions slice, such that all elements e1 from slice[0] 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 O(slice.length) evaluations of less and swap, with a worst case of O(slice.length^^2).
pivotPartition 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:
pivotPartitionImpl template pivotPartitionImpl(alias less): Undocumented in source.
sort template sort(alias less = "a < b"): Sorts ndslice, array, or series.
transitionIndex 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.

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

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

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

mir.ndslice.sorting

Members

Functions

Templates

Examples

See Also

Meta

Source

License

Copyright

Authors