std.algorithm.sorting

Это подмодуль std.algorithm. Он содержит обобщённые алгоритмы сортировки.

Лицензия:

Лицензия Boost 1.0.

Авторы:

Андрей Александреску

Исходный код

std/algorithm/sorting.d

alias SortOutput = std.typecons.Flag!"sortOutput".Flag;

Указывает, требуется ли вывод определённого алгоритма в отсортированном формате.

Если установлено в SortOutput.no, вывод не должен быть отсортированным.

В противном случае, если установлено в SortOutput.yes, вывод должен быть отсортированным.

void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less) lhs, Rhs rhs)
Constraints: if (hasLength!Rhs && hasSlicing!Rhs && hasSwappableElements!Lhs && hasSwappableElements!Rhs);

Сортирует диапазон произвольного доступа chain(lhs, rhs) согласно предикату less. Левая часть диапазона lhs предполагается уже отсортированной; rhs предполагается неотсортированной. Точная выбранная стратегия зависит от относительных размеров lhs и rhs. Выполняет Ο(lhs.length + rhs.length * log(rhs.length)) (лучший случай) до Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) (худший случай) вычислений swap.

Parameters:

less	Предикат для сортировки.
ss	Стратегия обмена.
SortedRange!(Lhs, less) lhs	Отсортированная левая часть диапазона произвольного доступа, подлежащая сортировке.
Rhs rhs	Неотсортированная правая часть диапазона произвольного доступа, подлежащая сортировке.

Examples:

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

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

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

Проверяет, является ли прямолинейный диапазон отсортированным согласно операции сравнения less. Выполняет Ο(r.length) вычислений less.

В отличие от isSorted, isStrictlyMonotonic не допускает одинаковых значений, т.е. значений, для которых и less(a, b), и less(b, a) ложны.

В обоих функциях предикат должен быть строгим упорядочением, как и в isSorted. Например, использование "a <= b" вместо "a < b" неверно и приведёт к ошибкам.

Parameters:

less	Предикат, по которому должен быть отсортирован диапазон.
Range r	Прямолинейный диапазон для проверки на отсортированность.

Returns:

true если диапазон отсортирован, иначе false. isSorted допускает дубликаты, isStrictlyMonotonic — нет.

Examples:

assert([1, 1, 2].isSorted);
// strictly monotonic doesn't allow duplicates
assert(![1, 1, 2].isStrictlyMonotonic);

int[] arr = [4, 3, 2, 1];
assert(!isSorted(arr));
assert(!isStrictlyMonotonic(arr));

assert(isSorted!"a > b"(arr));
assert(isStrictlyMonotonic!"a > b"(arr));

sort(arr);
assert(isSorted(arr));
assert(isStrictlyMonotonic(arr));

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

Как и isSorted, возвращает true если заданные values упорядочены согласно операции сравнения less. В отличие от isSorted, принимает значения напрямую вместо структурирования в диапазоне.

ordered допускает повторяющиеся значения, например, ordered(1, 1, 2) это true. Для проверки, что значения упорядочены строго монотонно, используйте strictlyOrdered; strictlyOrdered(1, 1, 2) это false.

В обоих функциях предикат должен быть строгим упорядочением. Например, использование "a <= b" вместо "a < b" неверно и приведёт к ошибкам.

Parameters:

T values	Тестируемое значение
less	Предикат сравнения

Returns:

true если значения упорядочены; ordered допускает дубликаты, strictlyOrdered — нет.

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, Range)(Range r)
Constraints: if (ss == SwapStrategy.stable && isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasSwappableElements!Range);

Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
Constraints: if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range);

Разделяет диапазон на две части, используя данный predicate. В частности, переупорядочивает диапазон r = [left, right) с использованием swap таким образом, чтобы все элементы i, для которых predicate(i) имеет значение true, стояли перед всеми элементами j, для которых predicate(j) возвращает false.

Выполняет Ο(r.length) (если неустойчивый или полуустойчивый) или Ο(r.length * log(r.length)) (если устойчивый) вычислений less и swap. Неустойчивая версия вычисляет минимальное возможное количество вычислений swap (примерно половину тех, что выполняются полуустойчивой версией).

Parameters:

predicate	Предикат для разделения.
ss	Стратегия обмена.
Range r	Диапазон произвольного доступа для разделения.

Returns:

Правая часть r после разделения. Если ss == SwapStrategy.stable, partition сохраняет относительный порядок всех элементов a, b в r для которых predicate(a) == predicate(b). Если ss == SwapStrategy.semistable, partition сохраняет относительный порядок всех элементов a, b в левой части r для которых predicate(a) == predicate(b).

Examples:

import std.algorithm.mutation : SwapStrategy;
import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;

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
writeln(r); // arr[5 .. $]
writeln(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);
writeln(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 .. $]);

size_t pivotPartition(alias less = "a < b", Range)(Range r, size_t pivot)
Constraints: if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);

Разделяет r вокруг pivot используя функцию сравнения less, алгоритм, аналогичный схеме разбиения Хоара. В частности, переставляет элементы r и возвращает индекс k < r.length такой, что:

• r[pivot] переставляется с r[k]



• Все элементы e в поддиапазоне r[0 .. k] удовлетворяют !less(r[k], e) (т.е. r[k] больше или равно каждому элементу слева в соответствии с предикатом less).



• Все элементы e в поддиапазоне r[k .. $] удовлетворяют !less(e, r[k]) (т.е. r[k] меньше или равно каждому элементу справа в соответствии с предикатом less).

Если r содержит эквивалентные элементы, несколько перестановок r удовлетворяют этим ограничениям. В таких случаях, pivotPartition пытается распределить эквивалентные элементы достаточно равномерно слева и справа от k, так что k остаётся рядом с r.length / 2.

Parameters:

less	Предикат, используемый для сравнения, моделируемый как строгое слабое упорядочение (иррефлексивное, антисимметричное, транзитивное и подразумевающее транзитивную эквивалентность)
Range r	Разделяемый диапазон
size_t pivot	Индекс опорного элемента для разбиения, должен быть меньше r.length или 0 если r.length это 0

Returns:

Новая позиция опорного элемента

See Also:

Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.

Examples:

int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
size_t pivot = pivotPartition(a, a.length / 2);
import std.algorithm.searching : all;
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));

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

Parameters:

pred	Предикат, по которому должен быть разделён диапазон.
Range r	Диапазон для проверки.

Returns:

true если r разделён согласно предикату 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)
Constraints: if (ss == SwapStrategy.unstable && isRandomAccessRange!Range && hasSwappableElements!Range && hasLength!Range && hasSlicing!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));

Переупорядочивает элементы в r в трех смежных диапазонах и возвращает их. Первый и самый левый диапазон содержит только элементы в r меньше pivot. Второй и средний диапазон содержит только элементы в r равные pivot. Наконец, третий и самый правый диапазон содержит только элементы в r больше pivot. Тест "меньше" определяется бинарной функцией less.

Параметры:

less	Предикат для использования при переупорядочивании.
ss	Стратегия перестановки для использования.
Диапазон r	Диапазон с произвольным доступом для переупорядочивания.
E pivot	Элемент-опорная точка.

Возвращаемое значение:

Кортеж std.typecons.Tuple из трех получившихся диапазонов. Эти диапазоны являются срезами исходного диапазона.

Ошибки:

Устойчивая partition3 еще не реализована.

Примеры:

auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
auto pieces = partition3(a, 4);
writeln(pieces[0]); // [1, 3]
writeln(pieces[1]); // [4, 4, 4]
writeln(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)
Constraints: if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*) && hasAssignableElements!RangeIndex);

void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index)
Constraints: if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex) && hasAssignableElements!RangeIndex);

Вычисляет индекс для r на основе сравнения less. Индекс — это отсортированный массив указателей или индексов в исходном диапазоне. Этот метод аналогичен сортировке, но более гибкий, поскольку (1) позволяет «сортировать» неизменяемые коллекции, (2) позволяет проводить бинарный поиск, даже если исходная коллекция не обеспечивает произвольного доступа, (3) позволяет использовать несколько индексов, каждый на разных предикатах, и (4) может быть быстрее при работе с большими объектами. Однако использование индекса также может быть медленнее в определенных обстоятельствах из-за дополнительной косвенности и всегда больше, чем решение на основе сортировки, поскольку оно требует памяти для индекса в дополнение к исходной коллекции. Сложность такая же, как у sort.

Первый перегруженный вариант makeIndex записывает в диапазон, содержащий указатели, а второй — в диапазон, содержащий смещения. Первый перегруженный вариант требует, чтобы Range был диапазоном с последовательным доступом, а второй — диапазоном с произвольным доступом.

makeIndex перезаписывает свой второй аргумент результатом, но никогда не перевыделяет его.

Параметры:

less	Используемое сравнение.
ss	Стратегия перестановки.
Диапазон r	Диапазон для индексирования.
RangeIndex index	Полученный индекс.

Возвращаемое значение:

Версия на основе указателей возвращает обёртку SortedRange над индексом типа SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)), отражающую порядок индекса. Версия на основе индексов возвращает void, поскольку отношение порядка включает не только index, но и r.

Исключения:

Если длина второго аргумента меньше длины индексируемого диапазона, выбрасывается исключение.

Примеры:

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

Merge!(less, Rs) merge(alias less = "a < b", Rs...)(Rs rs)
Constraints: if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

Объединяет несколько отсортированных диапазонов rs с предикатом меньше pred в один отсортированный выходной диапазон, содержащий отсортированное объединение элементов ввода. Дубликаты не удаляются, что означает, что общее количество элементов на выходе равно сумме всех элементов во входящих диапазонах; член length предлагается, если все входы также имеют length. Типы элементов всех входов должны иметь общий тип CommonType.

Параметры:

less	Предикат, по которому отсортированы заданные диапазоны.
Rs rs	Диапазоны для вычисления объединения.

Возвращаемое значение:

Диапазон, содержащий объединение заданных диапазонов.

Подробности

Все входящие диапазоны предполагаются отсортированными. Это может означать, что входы являются экземплярами std.range.SortedRange. Используйте результат std.algorithm.sorting.sort или std.range.assumeSorted, чтобы объединить известные отсортированные диапазоны (показано в примере ниже). Обратите внимание, что в настоящее время нет способа гарантировать, что два или более экземпляров std.range.SortedRange отсортированы с использованием определённой функции сравнения pred. Поэтому здесь не проверяется, чтобы все входящие rs были экземплярами std.range.SortedRange.

Этот алгоритм ленивый, выполняя работу поэтапно по мере извлечения элементов из результата. Время выполнения пропорционально сумме количества элементов во всех входах. Если все входы имеют одинаковый тип элементов и предоставляют его по ref, вывод становится диапазоном с изменяемыми front (и back при необходимости), которые отражаются в исходных входах. Если какой-либо из входов rs бесконечен, бесконечным будет и результат (empty всегда false).

См. также:

std.algorithm.setops.multiwayMerge для аналогичной функции объединения динамического количества диапазонов.

Примеры:

import std.algorithm.comparison : equal;
import std.range : retro;

int[] a = [1, 3, 5];
int[] b = [2, 3, 4];

assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));

Примеры:

тестирование двунаправленного доступа и общего типа

import std.algorithm.comparison : equal;
import std.range : retro;
import std.traits : CommonType;

alias S = short;
alias I = int;
alias D = double;

S[] a = [1, 2, 3];
I[] b = [50, 60];
D[] c = [10, 20, 30, 40];

auto m = merge(a, b, c);

static assert(is(typeof(m.front) == CommonType!(S, I, D)));

assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));

m.popFront();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
m.popBack();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
m.popFront();
assert(equal(m, [3, 10, 20, 30, 40, 50]));
m.popBack();
assert(equal(m, [3, 10, 20, 30, 40]));
m.popFront();
assert(equal(m, [10, 20, 30, 40]));
m.popBack();
assert(equal(m, [10, 20, 30]));
m.popFront();
assert(equal(m, [20, 30]));
m.popBack();
assert(equal(m, [20]));
m.popFront();
assert(m.empty);

template multiSort(less...)

Сортирует диапазон по нескольким ключам. Вызов multiSort!("a.id < b.id", "a.date > b.date")(r) сортирует диапазон r по id по возрастанию и сортирует элементы, имеющие одинаковое значение id по date по убыванию. Такой вызов эквивалентен sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), но multiSort быстрее, потому что выполняет меньше сравнений (помимо большей удобства).

Возвращаемое значение:

Исходный диапазон, обернутый как SortedRange с его предикатными функциями, преобразованными в эквивалентный единичный предикат.

Примеры:

import std.algorithm.mutation : SwapStrategy;
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);
writeln(pts1); // pts2

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

Сортирует диапазон с произвольным доступом в соответствии с предикатом less. Выполняет Ο(r.length * log(r.length)) вычислений less. Если less включает дорогостоящие вычисления для ключа сортировки, может быть целесообразно использовать schwartzSort вместо этого.

Устойчивая сортировка требует, чтобы hasAssignableElements!Range было true.

sort возвращает std.range.SortedRange над исходным диапазоном, позволяя функциям, которые могут использовать отсортированные данные, знать, что диапазон отсортирован, и соответственно корректировать поведение. std.range.SortedRange — это оболочка вокруг исходного диапазона, поэтому оба они отсортированы. Другие функции не могут знать, что исходный диапазон был отсортирован, но они *могут* знать, что std.range.SortedRange был отсортирован.

Предпосылки

От предиката ожидается соблюдение определённых правил, чтобы sort вело себя ожидаемым образом — в противном случае программа может завершиться неудачно на некоторых входных данных (но не на других), когда не скомпилирована в режиме выпуска, из-за поверхностной assumeSorted проверки. В частности, sort ожидает, что less(a,b) && less(b,c) подразумевает less(a,c) (транзитивность) и, наоборот, !less(a,b) && !less(b,c) подразумевает !less(a,c). Обратите внимание, что стандартный предикат ("a < b" ) не всегда удовлетворяет этим условиям для чисел с плавающей точкой, поскольку выражение всегда будет false когда либо a или b является NaN. Используйте std.math.cmp вместо этого.

Параметры:

less	Предикат для сортировки.
ss	Стратегия перестановки для использования.
Диапазон r	Диапазон для сортировки.

Возвращаемое значение:

Исходный диапазон, обернутый как SortedRange с предикатом binaryFun!less.

Алгоритмы

Introsort используется для неустойчивой сортировки, а Timsort — для устойчивой. Каждый алгоритм имеет преимущества помимо стабильности. Introsort обычно быстрее, но Timsort может достичь большей скорости на данных с низкой энтропией или если вызовы предикатов дорогостоящие. Introsort не выполняет выделений, тогда как Timsort выполнит одно или несколько выделений на вызов. Оба алгоритма имеют Ο(n log n) временную сложность в худшем случае.

См. также:

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

Примеры:

int[] array = [ 1, 2, 3, 4 ];

// sort in descending order
array.sort!("a > b");
writeln(array); // [4, 3, 2, 1]

// sort in ascending order
array.sort();
writeln(array); // [1, 2, 3, 4]

// sort with reusable comparator and chain
alias myComp = (x, y) => x > y;
writeln(array.sort!(myComp).release); // [4, 3, 2, 1]

Примеры:

// Showcase stable sorting
import std.algorithm.mutation : SwapStrategy;
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
writeln(words); // ["a", "aBc", "abc", "ABC", "b", "c"]

Примеры:

// Sorting floating-point numbers in presence of NaN
double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];

import std.algorithm.comparison : equal;
import std.math : cmp, isIdentical;

sort!((a, b) => cmp(a, b) < 0)(numbers);

double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
assert(numbers.equal!isIdentical(sorted));

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)
Constraints: if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R && !is(typeof(binaryFun!less) == SwapStrategy));

auto schwartzSort(alias transform, SwapStrategy ss, R)(R r)
Constraints: if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R);

Альтернативный метод сортировки, который следует использовать, когда сравнение ключей включает дорогостоящие вычисления. Вместо использования less(a, b) для сравнения элементов, schwartzSort использует less(transform(a), transform(b)). Значения функции transform предварительно вычисляются в временном массиве, тем самым экономя вычислительные ресурсы. И наоборот, если стоимость вычисления transform невелика по сравнению со стоимостью выделения и заполнения предварительно вычисленного массива, sort может быть быстрее и, следовательно, предпочтительнее.

Этот подход к сортировке аналогичен преобразованию Шварца, также известному как шаблон «декорировать-сортировать-распотрошить» в Python и Lisp. Сложность такая же, как у соответствующего sort, но schwartzSort вычисляет transform только r.length раз (менее чем в половину по сравнению с обычной сортировкой). Использование лучше всего проиллюстрировать на примере.

Пример

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

Функция schwartzSort может потребовать меньше временных данных и быть быстрее, чем фрагмент Perl или шаблон «декорировать-сортировать-распотрошить», присутствующий в Python и Lisp. Это происходит потому, что сортировка выполняется на месте и создается только минимально дополнительный объем данных (один массив преобразованных элементов). Чтобы проверить, был ли массив отсортирован, и воспользоваться ускорением сортировки Шварца, функция schwartzIsSorted не предоставляется, поскольку этого можно достичь, вызвав isSorted!less(map!transform(r)).

Параметры:

transform	Применяемая трансформация. Либо унарная функция (unaryFun!transform(element)), либо бинарная функция (binaryFun!transform(element, index)).
less	Предикат для сортировки преобразованных элементов.
ss	Используемая стратегия перестановки.
R r	Диапазон для сортировки.

Возвращаемое значение:

Исходный диапазон, обернутый как SortedRange с предикатом (a, b) => binaryFun!less(transform(a), transform(b)).

Примеры:

import std.algorithm.iteration : map;
import std.numeric : entropy;

auto lowEnt = [ 1.0, 0, 0 ],
     midEnt = [ 0.1, 0.1, 0.8 ],
    highEnt = [ 0.31, 0.29, 0.4 ];
auto arr = new double[][3];
arr[0] = midEnt;
arr[1] = lowEnt;
arr[2] = highEnt;

schwartzSort!(entropy, "a > b")(arr);

writeln(arr[0]); // highEnt
writeln(arr[1]); // midEnt
writeln(arr[2]); // lowEnt
assert(isSorted!("a > b")(map!(entropy)(arr)));

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

Переупорядочивает диапазон случайного доступа r таким образом, чтобы диапазон r[0 .. mid] был таким же, как если бы весь r был отсортирован, а диапазон r[mid .. r.length] не упорядочен определенным образом. Выполняет Ο(r.length * log(mid)) вычислений pred. Реализация просто вызывает topN!(less, ss)(r, n) и затем sort!(less, ss)(r[0 .. n]).

Параметры:

less	Предикат для сортировки.
ss	Используемая стратегия перестановки.
Range r	Диапазон случайного доступа, который нужно переупорядочить.
size_t n	Длина начального сегмента r для сортировки.

Примеры:

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

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

Хранит наименьшие элементы из двух диапазонов в левом диапазоне в отсортированном порядке.

Параметры:

less	Предикат для сортировки.
ss	Используемая стратегия перестановки.
Range1 r1	Первый диапазон.
Range2 r2	Второй диапазон.

Примеры:

int[] a = [5, 7, 2, 6, 7];
int[] b = [2, 1, 5, 6, 7, 3, 0];

partialSort(a, b);
writeln(a); // [0, 1, 2, 2, 3]

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

Переупорядочивает диапазон r с помощью swap так, что r[nth] ссылается на элемент, который там бы оказался, если бы диапазон был полностью отсортирован. Кроме того, он также разбивает r таким образом, что все элементы e1 от r[0] до r[nth] удовлетворяют !less(r[nth], e1), а все элементы e2 от r[nth] до r[r.length] удовлетворяют !less(e2, r[nth]). По сути, он находит n-й по величине (согласно less) элементы в r. Выполняет ожидаемое Ο(r.length) (если неустойчивая) или Ο(r.length * log(r.length)) (если устойчивая) вычислений less и swap.

Если n >= r.length, алгоритм не оказывает никакого влияния и возвращает r[0 .. r.length].

Параметры:

less	Предикат для сортировки.
ss	Используемая стратегия перестановки.
Range r	Диапазон случайного доступа для переупорядочения.
size_t nth	Индекс элемента, который должен быть в отсортированном положении после завершения функции.

См. также:

topNIndex,

Ошибки:

Устойчивый topN еще не реализован.

Примеры:

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

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

Хранит наименьшие элементы из двух диапазонов в левом диапазоне.

Параметры:

less	Предикат для сортировки.
ss	Используемая стратегия перестановки.
Range1 r1	Первый диапазон.
Range2 r2	Второй диапазон.

Примеры:

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

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

Копирует верхние n элементы входного диапазона source в диапазон случайного доступа target, где n = target.length. Элементы source не трогаются. Если sorted равно true, целевой диапазон отсортирован. В противном случае, целевой диапазон сохраняет свойство кучи.

Параметры:

less	Предикат для сортировки.
SRange source	Исходный диапазон.
TRange target	Целевой диапазон.
SortOutput sorted	Флаг сортировки копируемых элементов в target.

Возвращаемое значение:

Срез target, содержащий скопированные элементы.

Примеры:

import std.typecons : Yes;

int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
int[] b = new int[3];
topNCopy(a, b, Yes.sortOutput);
writeln(b); // [0, 1, 2]

void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index, SortOutput sorted = No.sortOutput)
Constraints: if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex);

Учитывая диапазон элементов, создает индекс его верхних n элементов (т.е., первых n элементов, если бы диапазон был отсортирован).

Аналогично topN, за исключением того, что диапазон не изменяется.

Параметры:

less	Бинарный предикат, определяющий порядок элементов диапазона. По умолчанию a < b.
ss	(Не реализовано.) Укажите стратегию перестановки.
Range r	Диапазон случайного доступа элементов, для которых нужно создать индекс.
RangeIndex index	Диапазон случайного доступа с присваиваемыми элементами для построения индекса. Длина этого диапазона определяет, сколько верхних элементов индексировать в r. Этот индексный диапазон может содержать целочисленные элементы, в таком случае создаваемый индекс будет содержать индексы с нулевой базой в r; или он может содержать указатели на тип элементов r, в таком случае создаваемый индекс будет указателями на верхние элементы в r.
SortOutput sorted	Определяет, следует ли сортировать индекс по элементам, на которые они ссылаются.

См. также:

topN, topNCopy.

Ошибки:

Параметр стратегии перестановки еще не реализован; в настоящее время он игнорируется.

Примеры:

import std.typecons : Yes;

// 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, Yes.sortOutput);
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, Yes.sortOutput);
writeln(ptrIndex); // [&a[5], &a[1], &a[3]]

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

Переставляет range на месте в следующую лексикографически большую перестановку.

Предикат less определяет лексикографический порядок, который будет использоваться для диапазона.

Если диапазон в настоящее время является лексикографически наибольшей перестановкой, он переставляется обратно в наименьшую перестановку, и возвращается false. В противном случае возвращается true. Таким образом, можно сгенерировать все перестановки диапазона, отсортировав его в соответствии с less, что даст лексикографически наименьшую перестановку, а затем вызывать nextPermutation до тех пор, пока он не вернёт false. Гарантируется, что это сгенерирует все различные перестановки диапазона ровно один раз. Если в диапазоне N элементов и все они уникальны, то будет сгенерировано N! перестановок. В противном случае, если есть некоторые повторяющиеся элементы, будет сгенерировано меньше перестановок.

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

Параметры:

less	Порядок, который будет использоваться для определения лексикографического порядка перестановок.
BidirectionalRange range	Диапазон для перестановки.

Возвращает:

false, если диапазон был лексикографически наибольшим, в этом случае диапазон возвращается к лексикографически наименьшей перестановке; в противном случае возвращает true.

См. также:

std.algorithm.iteration.permutations.

Примеры:

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

Примеры:

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

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

Переставляет range на месте в следующую лексикографически большую чётную перестановку.

Предикат less определяет лексикографический порядок, который будет использоваться для диапазона.

Чётная перестановка — это перестановка, которая получается путём обмена чётного количества пар элементов в исходном диапазоне. Множество чётных перестановок отличается от множества всех перестановок только тогда, когда в диапазоне нет повторяющихся элементов. Если диапазон содержит N уникальных элементов, то существует ровно N!/2 чётных перестановок.

Если диапазон уже является лексикографически наибольшей чётной перестановкой, он переставляется обратно в наименьшую чётную перестановку, и возвращается false. В противном случае возвращается true, и диапазон изменяется на месте, чтобы стать лексикографически следующей чётной перестановкой.

Таким образом, можно сгенерировать чётные перестановки диапазона с уникальными элементами, начиная с лексикографически наименьшей перестановки и многократно вызывая nextEvenPermutation, пока она не вернёт 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));

Также можно сгенерировать нечётные перестановки диапазона, заметив, что перестановки подчиняются правилу, что чётная + чётная = чётная, а нечётная + чётная = нечётная. Таким образом, поменяв последние два элемента лексикографически наименьшего диапазона, он превращается в первую нечётную перестановку. Затем, вызвав nextEvenPermutation для этой первой нечётной перестановки, будет сгенерирована следующая чётная перестановка относительно этой нечётной перестановки, которая фактически является следующей нечётной перестановкой исходного диапазона. Таким образом, вызывая многократно nextEvenPermutation, пока она не вернёт false, перечисляются нечётные перестановки исходного диапазона.

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

Предупреждение

Поскольку чётные перестановки отличаются от всех перестановок только в случае уникальности элементов диапазона, эта функция предполагает, что в диапазоне нет повторяющихся элементов при указанном порядке. Если это не так, некоторые перестановки могут не быть сгенерированы. Когда диапазон содержит не уникальные элементы, вы должны использовать nextPermutation вместо этого.

Параметры:

less	Порядок, который будет использоваться для определения лексикографического порядка перестановок.
BidirectionalRange range	Диапазон для перестановки.

Возвращает:

false, если диапазон был лексикографически наибольшим, в этом случае диапазон возвращается к лексикографически наименьшей перестановке; в противном случае возвращает true.

Примеры:

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

Примеры:

Чётные перестановки полезны для генерации координат некоторых геометрических фигур. Вот нетривиальный пример:

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));
}
writeln(n); // 60

ref Range nthPermutation(Range)(auto ref Range range, const ulong perm)
Constraints: if (isRandomAccessRange!Range && hasLength!Range);

Переставляет range в perm перестановку. Алгоритм имеет постоянную временную сложность относительно количества созданных перестановок. Из-за количества уникальных значений ulong только первые 21 элемент range могут быть переставлены. Остальная часть диапазона, следовательно, не будет переставлена. Этот алгоритм использует код Лемера.

Алгоритм работает следующим образом:

    auto pem = [4,0,4,1,0,0,0]; // permutation 2982 in factorial
    auto src = [0,1,2,3,4,5,6]; // the range to permutate


    auto i = 0;                    // range index
    // range index iterates pem and src in sync
    // pem[i] + i is used as index into src
    // first src[pem[i] + i] is stored in t
    auto t = 4;                    // tmp value
    src = [0,1,2,3,n,5,6];


    // then the values between i and pem[i] + i are moved one
    // to the right
    src = [n,0,1,2,3,5,6];
    // at last t is inserted into position i
    src = [4,0,1,2,3,5,6];
    // finally i is incremented
    ++i;


    // this process is repeated while i < pem.length


    t = 0;
    src = [4,n,1,2,3,5,6];
    src = [4,0,1,2,3,5,6];
    ++i;
    t = 6;
    src = [4,0,1,2,3,5,n];
    src = [4,0,n,1,2,3,5];
    src = [4,0,6,1,2,3,5];

Возвращает:

Переставленный диапазон.

Параметры:

Range range	Диапазон для перестановки. Исходный порядок будет потерян.
ulong perm	Перестановка, в которую необходимо переставить range .

Примеры:

auto src = [0, 1, 2, 3, 4, 5, 6];
auto rslt = [4, 0, 6, 2, 1, 3, 5];

src = nthPermutation(src, 2982);
writeln(src); // rslt

bool nthPermutationImpl(Range)(auto ref Range range, ulong perm)
Constraints: if (isRandomAccessRange!Range && hasLength!Range);

Возвращает:

true в случае успешной перестановки, false в случае, если у perm было больше цифр в системе факториалов, чем элементов в диапазоне. Этот случай не должен возникать, так как это приведёт к обращениям к элементам за пределами диапазона.

Примеры:

auto src = [0, 1, 2, 3, 4, 5, 6];
auto rslt = [4, 0, 6, 2, 1, 3, 5];

bool worked = nthPermutationImpl(src, 2982);
assert(worked);
writeln(src); // rslt