std.algorithm.sorting

Переместиться к: completeSort · isPartitioned · isSorted · isStrictlyMonotonic · makeIndex · Merge · merge · multiSort · nextEvenPermutation · nextPermutation · ordered · partialSort · partition · partition3 · pivotPartition · schwartzSort · sort · SortOutput · strictlyOrdered · topN · topNCopy · topNIndex

Это подмодуль модуля std.algorithm. Он содержит типовые алгоритмы сортировки.
Шпаргалка
Имя функции Описание
completeSort Если a = [10, 20, 30] и b = [40, 6, 15], тогда completeSort(a, b) оставляет a = [6, 10, 15] и b = [20, 30, 40]. Диапазон a должен быть отсортирован до вызова, и результатом будет отсортированная комбинация std.range.chain(a, b).
isPartitioned isPartitioned!"a < 0"([-1, -2, 1, 0, 2]) возвращает true , поскольку предикат возвращает истину для части диапазона и ложь в конце.
isSorted isSorted([1, 1, 2, 3]) возвращает true.
isStrictlyMonotonic isStrictlyMonotonic([1, 1, 2, 3]) возвращает false.
ordered ordered(1, 1, 2, 3) возвращает true.
strictlyOrdered strictlyOrdered(1, 1, 2, 3) возвращает false.
makeIndex Создает отдельный индекс для диапазона.
merge Лениво объединяет два или более отсортированных диапазона.
multiSort Сортирует по нескольким ключам.
nextEvenPermutation Вычисляет следующую четную лексикографически бОльшую перестановку диапазона на-месте.
nextPermutation Вычисляет следующую лексикографически бОльшую перестановку диапазона на-месте.
partialSort Если a = [5, 4, 3, 2, 1], тогда partialSort(a, 3) даст a[0 .. 3] = [1, 2, 3]. Другие элементы a оставляются в неопределенном порядке.
partition Разделяет диапазон согласно одноаргументному предикату.
partition3 Разделяет диапазон согласно двухаргументному предикату на три части (меньше чем, равный, больше чем данный pivot). pivot принимается не как индекс, а как элемент, независимый от содержимого диапазона.
pivotPartition Разделяет диапазон согласно двухаргументному предикату на две части: меньше чем или равный, и больше чем или равный данному pivot, переданному как индекс в диапазоне.
schwartzSort Сортирует с помощью Преобразования Шварца.
sort Сортировка.
topN Отделяет верхние элементы в диапазоне. (Здесь и в следующих двух функциях слово "верхние" означает "первые из отсортированного диапазона". Кому как, а для меня это было не сразу очевидно. – прим. пер.)
topNCopy Копирует верхние элементы диапазона.
topNIndex Строит индекс верхних элементов диапазона.
Лицензия:
Boost License 1.0.
Авторы:
Andrei Alexandrescu

Исходный код: 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, Range1, Range2)(SortedRange!(Range1, less) lhs, Range2 rhs)
if (hasLength!Range2 && hasSlicing!Range2);
Сортирует цепь диапазонов с произвольным доступом 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.
Параметры:
less Предикат для сортировки.
ss Используемая стратегия обмена.
SortedRange!(Range1, less) lhs Отсортированная, левая сторона диапазона с произвольным доступом.
Range2 rhs Неотсортированная, правая сторона диапазона с произвольным доступом.
Примеры:
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);

bool isStrictlyMonotonic(alias less = "a < b", Range)(Range r)
if (isForwardRange!Range);
Проверяет, отсортирован ли лидирующий диапазон согласно операции сравнения less. Выполняет Ο(r.length) вычислений less.
В отличие от isSorted, isStrictlyMonotonic не допускает равные значения, то есть такие, для которых как less(a, b), так и less(b, a) возвращают false.
С каждой из функций, предикат должен давать строгое упорядочение. Например, использование "a <= b" вместо "a < b" некорректно и вызовет сообщение об ошибке.
Параметры:
less Предикат, в соответсвии с которым должен быть отсортирован диапазон.
Range r Лидирующий диапазон, который проверяется на наличие сортировки.
Возвращает:
true если диапазон отсортирован, false в противном случае. isSorted допускает дубликаты, isStrictlyMonotonic – нет.
Примеры:
assert([1, 1, 2].isSorted);
// строгая монотонность не допускает дубликатов
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)
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))));
Подобно isSorted, возвращает true, если данные величины values упорядочены согласно операции сравнения less. В отличие от isSorted, принимает величины непосредственно, а не структурированные в диапазоне.
ordered допускает повторения values, т.е. ordered(1, 1, 2) возвратит true. Чтобы проверить, что values упорядочены строго монотонно, используйте strictlyOrdered; strictlyOrdered(1, 1, 2) возвратит false.
С каждой из функций, предикат должен давать строгое упорядочение. Например, использование "a <= b" вместо "a < b" некорректно и вызовет сообщение об ошибке.
Параметры:
T values Тестируемые значения
less Сравнивающий предикат
Возвращает:
true если значения упорядочены; ordered допускает дубликаты, strictlyOrdered – нет.
Примеры:
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));
// Упорядочены лексикографически
assert(ordered("Jane", "Jim", "Joe"));
assert(strictlyOrdered("Jane", "Jim", "Joe"));
// Между прочим, они также упорядочены по уменьшению длины
assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
// ... но не строго, так как "Jim" и "Joe" имеют одинаковую длину
assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
Range partition(alias predicate, SwapStrategy ss, Range)(Range r)
if (ss == SwapStrategy.stable && isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);

Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range);
Разделяет диапазон на два, используя данный предикат predicate. В частности, переупорядочивает диапазон r = [left, right), используя обмен так, что все элементы i, для которых predicate(i) возвращает истину, предшествуют всем элементам j, для которых predicate(j) возвращает ложь.
Выполняет Ο(r.length) (для unstable или semistable) или Ο(r.length * log(r.length)) (для stable) вычислений less и операций обмена. Неустойчивая (unstable) версия выполняет минимально возможное количество операций обмена (приблизительно половина от выполняемых полуустойчивой (semistable) версией).
Параметры:
predicate Предикат, в соотвествии с которым происходит разделение.
ss Применяемая стратегия обмена.
Range r Разделяемый диапазон с произвольным доступом.
Возвращает:
Правая часть r после разделения.
Если ss == SwapStrategy.stable, partition сохраняет относительное упорядочение всех элементов a, b в r для которых predicate(a) == predicate(b). Если ss == SwapStrategy.semistable, partition сохраняет относительное упорядочение всех элементов a, b в левой части r для которых predicate(a) == predicate(b).
Смотрите также:
Примеры:
import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;
import std.algorithm.mutation : SwapStrategy;

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; }
// Разделяет arr так, чтобы четные числа были на первом месте
auto r = partition!(even)(arr);
// Теперь arr разделен на четные и нечетные.
// Числа могут переместиться из-за нестабильности
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);

// Может также определить предикат как строку.
// Используйте 'a' как имя аргумента предиката
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);

// Теперь для стабильного разделения:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Теперь arr - это [2 4 6 8 10 1 3 5 7 9], и r указывает на 1
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// В случае, если предикату нужно удерживать своё собственноё состояние, используйте делегат:
arr[] = Arr[];
int x = 3;
// Разместить всё, что больше, чем 3, слева
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Теперь arr - это [4 5 6 7 8 9 10 2 3 1] и r указывает на 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)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Слово "pivot", как это бывает с большинством слов в английском языке, имеет кучу значений. Тут и далее я решил придерживаться значения, используемого в 3D-графике – "опорная точка" – прим. пер.
Разделяет 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.
Параметры:
less Предикат, используемый для сравнения, смоделированный как строгое слабое упорядочение (нерефлексивное, антисимметричное, транзитивное, и подразумевающее переходную эквивалентность)
Range r Разделяемый диапазон
size_t pivot Индекс опорной точки для разбиения, должен быть меньше, чем r.length
Возвращает:
Новая позиция pivot
Смотрите также:
Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.
Примеры:
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)
if (isForwardRange!Range);
Параметры:
pred Предикат, в соответсвии с которым диапазон должен быть разделен.
Range r Проверяемый диапазон.
Возвращает:
true, если r разделен в зависимости от предиката pred.
Примеры:
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 && 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 Используемая стратегия обмена.
Range r Диапазон с произвольным доступом для перестройки.
E pivot Элемент – опорная точка.
Возвращает:
Кортеж std.typecons.Tuple из трех получившихся диапазонов. Эти диапазоны являются срезами исходного диапазона.
Недостатки:
стабильная стратегия для partition3 ещё пока не реализована.
Примеры:
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));
Вычисляет индекс index для r, основанный на сравнении less. index – это отсортированный массив указателей или индексов в исходном диапазоне. Эта техника подобна сортировке, но более гибкая, поскольку (1) она допускает "сортировку" неизменяемых (immutable) коллекций, (2) допускает двоичный поиск, даже если исходная коллекция не предлагает произвольный доступ, (3) допускает множественные индексы, каждый со своим предикатом, и (4) может быть более быстрой при работе с большими объектами. Тем не менее, использование index может также быть медленным при определенных обстоятельствах из-за дополнительной косвенности, и всегда использует больше памяти, чем решения, основанные на сортировке, поскольку, для индекса нужно пространство в дополнение к исходной коллекции. Сложность такая же, как и у sort.
Первая перегрузка makeIndex пишет в диапазон, содержащий указатели, вторая пишет в диапазон, содержащий смещения. Первая перегрузка требует, чтобы Range был лидирующим диапазоном, последняя требует, чтобы он был диапазоном с произвольным доступом.
makeIndex перезаписывает результат в свой второй аргумент, но никогда не перераспределяет его.
Параметры:
less Используемое сравнение.
ss Стратегия обмена.
Range r Диапазон для построения индекса.
RangeIndex index Результирующий индекс.
Возвращает:
Версия, основанная на указателях, возвращает обёртку SortedRange над индексом, с типом SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) , таким образом отражая упорядочение индекса. Версия, основанная на индексах, возвращает void, поскольку упорядочивающее отношение включает в себя не только index, но также r.
Исключения:
Если длина второго аргумента меньше, чем длина самого индексируемого диапазона, выбрасывается исключение.
Примеры:
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// индекс, использующий указатели
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// индекс, использующий смещения
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));

Переместиться к: empty · front · length · opDollar · popFront · save · this

struct Merge(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));

Merge!(less, Rs) merge(alias less = "a < b", Rs...)(Rs rs);
Лениво вычисляет объединение двух или больше диапазонов rs. Принимается, что диапазоны отсортированы предикатом less. Элементы на выходе не уникальные; длина выхода является суммой длин входов. (Свойство длины length предоставляется, если все диапазоны также имеют длину.) Типы элементов всех диапазонов должны иметь общий тип.
Параметры:
less Предикат, в соответствии с которым данные диапазоны отсортированы.
Rs rs Диапазоны для вычисления объединения.
Возвращает:
Диапазон, содержащий объединение данных диапазонов.
Примеры:
import std.algorithm.comparison : equal;

int[] a = [1, 3, 5];
int[] b = [2, 3, 4];
assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
this(Rs rs);
@property bool empty();
void popFront();
@property ref ElementType front();
@property auto save();
@property size_t length();
alias opDollar = length;
template multiSort(less...)
auto multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, 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 со своими предикатами, преобразованными в эквиалентный единичный предикат.
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);
Сортирует диапазон с произвольным доступом в соответсвии с предикатом 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 Используемая стратегия обмена.
Range r Диапазон для сортировки.
Возвращает:
Исходный диапазон, завёрнутый в SortedRange с предикатом binaryFun!less.

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

Примеры:
int[] array = [ 1, 2, 3, 4 ];

// сортировка в нисходящем порядке
array.sort!("a > b");
assert(array == [ 4, 3, 2, 1 ]);

// сортировка в возрастающем порядке
array.sort();
assert(array == [ 1, 2, 3, 4 ]);

// сортировка с многократно используемым компаратором и цепью
alias myComp = (x, y) => x > y;
assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
Примеры:
// Демонтрация стабильной сортировки
import std.algorithm.mutation : SwapStrategy;
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
Примеры:
// Сортировка чисел с плавающей запятой в присутствии NaN
double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];

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

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)
if (isRandomAccessRange!R && hasLength!R);
Альтернативный метод сортировки, который нужно использовать, когда сравнение ключей включает дорогое вычисление. Вместо использования less(a, b) для сравнения элементов, schwartzSort использует less(transform(a), transform(b)). Значения функции transform заранее вычисляются во временный массив, таким образом предотвращая её многократное вычисление. И наоборот, если стоимость transform небольшая по сравнению со стоимостью распределения памяти и заполнением предвычисленного массива, sort может оказаться более быстрой и, следовательно, предпочтительной.
Этот метод сортировки родственен Преобразованию Шварца, также известному как шаблон decorate-sort-undecorate в языках Python и Lisp. Сложность такая же, как и у соответствующей sort, но schwartzSort вычисляет transform только r.length раз (меньше половины по сравнению с обычной сортировкой). Использование лучше всего можно проиллюстрировать на примере.

Example:

uint hashFun(string) { ... дорогое вычисление ... }
string[] array = ...;
// Сортировка строк по хэшу, медленно
sort!((a, b) => hashFun(a) < hashFun(b))(array);
// Сортировка строк по хэшу, быстро (вычисляется только arr.length хэшей):
schwartzSort!(hashFun, "a < b")(array);
Функция schwartzSort может потребовать меньше временных данных и быть быстрее, чем идиома Perl или идиома decorate-sort-undecorate, представленная в Python и Lisp. Дело в том, что сортировка выполняется на-месте и создаются только минимальные дополнительные данные (один массив преобразованных элементов).
Проверить, был ли отсортирован массив, можно вызовом isSorted!less(map!transform(r)).

Параметры:
transform Применяемое преобразование.
less Сортирующий предикат.
ss Стратегия обмена.
R r Диапазон для сортировки.
Возвращает:
Исходный диапазон, завёрнутый в SortedRange с предикатом (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);
Переупорядочивает диапазон с произвольным доступом 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);
assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);

Переместиться к: 2

auto topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Переупорядочивает с использованием обмена диапазон r так, что 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) (при unstable) или Ο(r.length * log(r.length)) (при stable) вычислений less и операций обмена.
Если n >= r.length, алгоритм не имеет эффекта и возвращает r[0 .. r.length].
Параметры:
less Предикат для сортировки.
ss Используемая стратегия обмена.
Range r Переупорядочиваемый диапазон с произвольным доступом.
size_t nth Индекс элемента, который должен оказаться в отсортированной позиции после выполнения функции.
Смотрите также:
Недостатки:
Стабильная версия topN пока не реализована.
Примеры:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
topN!"a < b"(v, 100);
assert(v == [ 25, 7, 9, 2, 0, 5, 21 ]);
auto n = 4;
topN!"a < b"(v, n);
assert(v[n] == 9);
auto 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));
Сохраняет самые маленькие элементы двух диапазонов в диапазоне слева.
Параметры:
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);
assert(a == [0, 1, 2, 2, 3]);
TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = No.sortOutput)
if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);
Копирует верхние n элементов входного диапазона source (источник) в диапазон с произвольным доступом target (цель), где n = target.length. Элементы source остаются нетронутыми. Если sorted равно true, target будет отсортирована. В противном случае, target соблюдает Двоичную кучу.
Параметры:
less Предикат для сортировки.
SRange source Диапазон – источник.
TRange target Диапазон – цель.
SortOutput sorted Сортировать ли элементы, скопированные в target.
Возвращает:
Срез target, содержащий скопированные элементы.
Примеры:
int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
int[] b = new int[3];
topNCopy(a, b, Yes.sortOutput);
assert(b == [ 0, 1, 2 ]);
void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index, SortOutput sorted = No.sortOutput)
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 = No.sortOutput)
if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex && is(ElementType!RangeIndex == ElementType!Range*));
Дан диапазон элементов, создается индекс index его верхних n элементов (то есть, первые n элементов, если бы диапазон был отсортирован).
Похоже на topN, за исключением того, что диапазон не модифицируется.
Параметры:
less Двухаргументный предикат, который определяет упорядочение элементов диапазона. Устанавливается по умолчанию в a < b.
ss (Пока не реализовано.) Используемая стратегия обмена.
Range r Диапазон с произвольным доступом элементов, для которого создаётся индекс.
RangeIndex index Диапазон с произвольным доступом с присваиваемыми элементами, в котором строится индекс. Длина этого диапазона определяет, сколько верхних элементов в rбудет проиндексировано.
Элементы этого индексного диапазона могут быть целыми числами, в этом случае конструируемый индекс будет состоять из начинающихся с нуля цифровых индексов в r; или они могут быть указателями на тип элементов r, в этом случае конструируемый индекс будет указателями на верхние элементы в r.
SortOutput sorted Определяет, сортировать ли index по элементам, на которые они ссылаются.
Смотрите также:
Недостатки:
Параметр стратегии обмена пока не реализован; в настоящее время игнорируется.
Примеры:
// Создать индекс для верхних 3 элементов, с использованием цифровых индексов:
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

// Создать индекс для верхних 3 элементов, с использованием индексов-указателей:
int*[] ptrIndex = new int*[3];
topNIndex(a, ptrIndex, Yes.sortOutput);
assert(ptrIndex == [ &a[5], &a[1], &a[3] ]);
bool nextPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRange range)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
Переставляет диапазон range на-месте к следующей лексикографически бОльшей перестановке.
Предикат less определяет лексикографический порядок, который будет использоваться.
Если диапазон является к настоящему времени лексикографически самой большой перестановкой, он переставляется в наименьшую перестановку и возвращается false. В противном случае, возвращается true. Таким образом можно сгенерировать все перестановки диапазона, отсортировав его согласно less, что произведёт лексикографически наименьшую перестановку, и затем вызывая nextPermutation, пока она не возвратит false. Это гарантирует генерацию всех различных перестановок диапазона точно по одному разу. Если в дипазоне присутсвуют N элементов и все они уникальные, тогда будет сгенерировано N! перестановок. В противном случае, если есть несколько дублированных элементов, будет произведено меньше перестановок.
// Перечислить все перестановки
int[] a = [1,2,3,4,5];
do
{
    // использовать текущую перестановку и перейти 
    // к следующей перестановке массива.
} while (nextPermutation(a));
Параметры:
less Этот предикат будет использоваться для определения лексикографического порядка перестановок.
BidirectionalRange range Переставляемый диапазон.
Возвращает:
false, если диапазон был лексикографически самым большим, в этом случае диапазон возвращается на лексикографически минимальную перестановку; в противном случае возвращается true.
Смотрите также:
Примеры:
// Шаги через все перестановки сортированного массива в лексикографическом порядке
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]);
Примеры:
// Шаги через перестановки массива, содержащего дублированные элементы:
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);
Переставляет диапазон range на-месте к следующей лексикографически бОльшей чётной перестановке.
Предикат less определяет лексикографический порядок, который будет использоваться.
Чётной перестановкой является та, которая получается путем замены чётного числа пар элементов в исходном диапазоне. Множество чётных перестановок отличается от множества всех перестановок только тогда, когда нет повторяющихся элементов в диапазоне. Если диапазон имеет N уникальных элементов, тогда существует точно N!/2 чётных перестановок.
Если диапазон является к настоящему времени лексикографически самой большой перестановкой, он переставляется в наименьшую перестановку и возвращается false. В противном случае, возвращается true , и диапазон модифицируется на-месте в лексикографически следующую чётную перестановку.
Таким образом можно сгенерировать чётные перестановки диапазона с уникальными элементами начиная с лексикографически минимальной перестановки, и многократно вызывая nextEvenPermutation, пока он не возвратит false.
// Перечислить чётные перестановки
int[] a = [1,2,3,4,5];
do
{
    // использовать текущую перестановку и перейти 
    // к следующей чётной перестановке массива.
} while (nextEvenPermutation(a));
Можно также сгенерировать нечётные перестановки замечая, что перестановки следуют правилу, что чётный + чётный = чётный, и нечётный + чётный = нечётный. Таким образом, обмен последних двух элементов в лексикографически наименьшем диапазоне, формирует первую нечётную перестановку. Затем, вызов nextEvenPermutation на этой первой нечётной перестановке сгенерирует следующую чётную перестановку относительно этой нечётной перестановки, которая будет являться следующей нечётной перестановкой исходного диапазона. Таким образом, многократно вызывая nextEvenPermutation, пока не возвратится false, можно получить перечисление нечётных перестановок исходного диапазона.
// Перечислить нечётные перестановки
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]);    // а является теперь первой нечётной перестановкой [1,2,3,4,5]
do
{
    // использовать текущую перестановку и перейти 
    // к следующей нечётной перестановке исходного массива.
    // (который является чётной перестановкой первой нечётной перестановки).
} while (nextEvenPermutation(a));

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

Параметры:
less Этот предикат будет использоваться для определения лексикографического порядка перестановок.
BidirectionalRange range Переставляемый диапазон.
Возвращает:
false, если диапазон был лексикографически самым большим, в этом случае диапазон возвращается на лексикографически минимальную перестановку; в противном случае возвращается true.
Примеры:
// Шаги через чётные перестановки сортированного массива в лексикографическом порядке
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]);
Примеры:
Чётные перестановки полезны для генерации координат определенных геометрических форм. Вот нетривиальный пример:
import std.math : sqrt;

// Напечатать 60 вершин однородного усеченного икосаэдра (футбольного мяча)
enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Золотое сечение
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)
{
    // Цикл по чётным перестановкам каждого seed
    do
    {
        // Цикл по всем изменениям знака каждой перестановки
        size_t i;
        do
        {
            // Сгенерировать все возможные изменения знака
            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);