std.algorithm.sorting

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)
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)) (最悪の場合)のスワップ評価を実行する。

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)
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) の両方が偽となる値である。

どちらの関数でも、述語は厳密な順序でなければならない。 isSorted.例えば、"a < b" の代わりに"a <= b" を使うのは正しくない。 の代わりに を使うのは正しくない。

Parameters:

less	ソートされるべき範囲の述語。
Range r	ソートされているかどうかをチェックする前方範囲。

Returns:

true ソートされていればfalseを返す。 isSorted許可する 重複を許す、 isStrictlyMonotonicではない。

Examples:

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は、例えば以下のように、繰り返し値を取ることができる。 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));
// 辞書順に並べる
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 && hasSwappableElements!Range);

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

与えられたpredicate を使って、範囲を2つに分割する。

具体的には r = [left, right)スワップを使って を使って、predicate(i) がtrue であるすべての要素i が、 が を返すすべての要素 より前に来るように、範囲を並べ替える。 predicate(j) がfalse を返すすべての要素j の前に来るようにする。

Ο(r.length) (不安定または半安定な場合) またはΟ(r.length * log(r.length)) (安定な場合) を実行し、less とswap を評価する。 不安定バージョンは、 と 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; }
// 偶数が最初に来るようにarrを分割する
auto r = partition!(even)(arr);
// これでarrは偶数と確率に分かれる。
// 不安定なため、数字がシャッフルされている可能性がある
writeln(r); // arr[5 .. $]
writeln(count!(even)(arr[0 .. 5])); // 5
assert(find!(even)(r).empty);

// 述語を文字列で指定することもできる。
// 述語の引数名として'a'を使用する
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
writeln(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 && hasAssignableElements!Range);

パーティション rを中心に pivot比較関数less 、Hoareパーティションに似たアルゴリズムを用いている。 に似ている。

具体的には 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 がr.length / 2 の近くにとどまるように、k の左右に等価な要素を配分しようとする。

Parameters:

less	比較に使われる述語は、次のようにモデル化される。 としてモデル化される。 等価を意味する)
Range r	分割される範囲
size_t pivot	分割のピボットのインデックス。 r.lengthまたは 0 もし r.lengthである。0

Returns:

ピボットの新しい位置

See Also:

クイックソートのエンジニアリングPartitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. 2011年2月ACCU 2016基調講演、アンドレイ・アレキサンドレスク。

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

の要素を隣接する3つの範囲で並べ替える。 rの要素を隣接する3つの範囲で並べ替えて返す。 返す。

一番左の範囲には r 未満の要素しか含まない。 pivot.2番目と真ん中の範囲には の要素のみを含む。 rに等しい pivot.最後に、3番目の の要素のみを含む。 rの要素だけが含まれる。 よりも大きい pivot.より小さいかどうかのテストはバイナリ関数で定義される。 less.

Parameters:

less	並べ替えに使う述語。
ss	使用するスワッピング戦略。
Range r	再配置するランダムアクセス範囲。
E pivot	ピボット要素。

Returns:

A std.typecons.Tupleである。これらの範囲は のスライスである。

Bugs:

安定した partition3はまだ実装されていない。

Examples:

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)
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)
if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex) && hasAssignableElements!RangeIndex);

のインデックスを計算する。 rlessのインデックスを計算する。

インデックスは、元の範囲へのポインタまたはインデックスのソートされた配列である。 範囲へのポインタまたはインデックスのソート配列である。このテクニックはソートに似ているが、より柔軟である。 なぜなら、(1)不変のコレクションを「ソート」できるからである。 バイナリ検索ができる。 (3)異なる述語に対する複数のインデックスが可能である、 (4)大きなオブジェクトを扱う場合、より高速になる可能性がある。しかし インデックスを使用すると、余分な間接処理のために特定の状況下では遅くなることがある。 また、ソートベースの解決策よりも常に大きくなる。 というのも、元のコレクションに加えてインデックス用のスペースが必要になるからである。 また、元のコレクションに加えてインデックス用のスペースも必要となるため、ソートベースのソリューションよりも常に大きくなる。複雑さはsort'と同じである。

の最初のオーバーロードは makeIndexの最初のオーバーロードは ポインターを含む範囲に書き込む。最初のオーバーロードは 最初のオーバーロードは、Range が フォワード範囲であることが要求される。 後者はランダムアクセス範囲であることを要求する。

makeIndexは第2引数を結果で上書きするが、再割り当てすることはない。 を再割り当てすることはない。

Parameters:

less	使用する比較対象
ss	スワップ戦略。
Range r	インデックスを作成する範囲。
RangeIndex index	結果のインデックス。

Returns:

ポインタベースのバージョンは、SortedRange のラッパーを返す。 を返す。 SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) 型の 型である。インデックスベースのバージョンはvoid を返す。 関係には indexだけでなく r.

Throws:

第2引数の長さが、インデックスされた範囲 のインデックスより小さい場合は例外がスローされる。

Examples:

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

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

複数のソートされた範囲をマージする rsを小なり述語関数でマージする。pred を持つ複数のソート範囲を、入力の要素のソート共用体を含む1つのソートされた出力範囲にマージする。 要素を含む1つのソートされた出力範囲にマージする。

重複は除去されない。 つまり、出力の要素の総数は、渡された範囲の要素の総和となる。 を持つ場合、length のメンバが提供される。 length.すべての入力の要素型は共通の型でなければならない。 CommonType.

Parameters:

less	与えられた範囲を述語でソートする。
Rs rs	について共用体を計算する範囲。

Returns:

与えられた範囲の共用体を含む範囲。

詳細 すべての入力はソートされていると仮定される。これは、入力が のインスタンスであることを意味する。 std.range.SortedRange.の結果を使用する。 std.algorithm.sorting.sortまたは std.range.assumeSortedの結果を使う。 の結果を使うか、またはソートされていることが分かっている範囲をマージする(下の例)。現在のところ の2つ以上のインスタンスがソートされていることを保証する方法は今のところない。 std.range.SortedRangeの2つ以上のインスタンスが特定の比較関数pred を使用してソートされていることを保証する方法は今のところないことに注意すること。したがって のインスタンスであることを保証するためのチェックは行われない。 rsのインスタンスであることを保証するためのチェックは行われない。 std.range.SortedRange.

このアルゴリズムは遅延的であり、要素が結果から引き抜かれるにつれて漸進的に作業を行う。 を行う。

時間の複雑さは、すべての入力の要素数の合計に比例する。

すべての入力が同じ要素型を持ち、それをref 、出力する。 は変更可能なfront (適切な場合はback )を持つ範囲となる。 に反映される。

入力のどれかが rsが無限であれば、結果も無限である(empty は常に false).

See Also:

std.algorithm.setops.multiwayMerge類似の関数である を使うことができる。

Examples:

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

Examples:

テスト双方向アクセスと共通型

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と同等であるが このような呼び出しは、 と同等であるが、(より便利であることに加えて)比較回 数が少ないため、より高速である。

Returns:

初期範囲は、SortedRange 、その述語は同等の単一述語に変換される。 を等価な単一の述語に変換する。

Examples:

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

ランダムアクセス範囲を述語less に従ってソートする。

less less をΟ(r.length * log(r.length))回評価する。 を実行する。 ソートキーに高価な計算が含まれる場合は、以下のようにする。 schwartzSortを使う価値があるかもしれない。

安定したソートには、hasAssignableElements!Range が真であることが必要である。

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" )は、浮動小数点型に対してこれらの条件を常に満たすわけではないことに注釈:。 は、浮動小数点型では常にこれらの条件を満たさない。 は、a またはb のいずれかがNaNのとき、常にfalse になるからである。 代わりに std.math.cmpを使う。

Parameters:

less	ソートする述語。
ss	使用するスワッピング戦略。
Range r	ソートする範囲。

Returns:

最初の範囲は、述語SortedRange 。 binaryFun!less.

アルゴリズム イントロソートは不安定なソートに使われ ティムソートは安定したソートに使われる。 それぞれのアルゴリズムには安定性以外の利点もある。イントロソートは一般的に高速だが ティムソートは、エントロピーの低いデータや述語の呼び出しが高価な場合に、より高速になる可能性がある は高価である。Introsortはアロケーションを行わないが、Timsortは呼び出しごとに1つ以上のアロケーションを行う。 を実行する。どちらのアルゴリズムも、最悪ケースでΟ(n log n)の時間複雑性を持つ。 の時間複雑性を持つ。

See Also:

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

Examples:

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

// 降順にソートする
array.sort!("a > b");
writeln(array); // [4, 3, 2, 1]

// 昇順にソートする
array.sort();
writeln(array); // [1, 2, 3, 4]

// 再使用可能なコンパレータとchainでソートする
alias myComp = (x, y) => x > y;
writeln(array.sort!(myComp).release); // [4, 3, 2, 1]

Examples:

// 安定した選別
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"]

Examples:

// NaNが存在する場合の浮動小数点数のソート
double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];

import std.algorithm.comparison : equal;
import std.math.operations : cmp;
import std.math.traits : 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)
if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R && !is(typeof(binaryFun!less) == SwapStrategy));

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

キーの比較に高価な計算が必要な場合、別のソート方法を使うべきである。 を使うべきである。

要素の比較にless(a, b) 、 schwartzSortless(transform(a), transform(b))を使用する。を使用する。 transform 関数の値は一時配列で事前に計算されるので、繰り返し計算する手間が省ける。 繰り返し計算する手間が省ける。逆に、transform のコストが、事前計算された配列の割り当てと充填のコストに比べて小さい場合は、 を使用する。 のコストが、事前計算された配列の確保と充填のコストに比べて小さい場合は、 を使用する、sort の方が高速であり、望ましい。

このソートのアプローチは、シュワルツ変換に似ている。 PythonやLispのdecorate-sort-undecorateパターンとしても知られている。複雑さは、対応する は対応するsort と同じである。 schwartzSortを評価する transform を評価する r.length回しか評価されない(通常の である。)この使い方は、例で説明するのが一番わかりやすいだろう。

例:

uint hashFun(string) { ... expensive computation ... }
string[] array = ...;
// ハッシュで文字列をソートする、遅い
sort!((a, b) => hashFun(a) < hashFun(b))(array);
// ハッシュ値で文字列を高速にソートする(arr.lengthハッシュ値のみを計算する):
schwartzSort!(hashFun, "a < b")(array);

例えば schwartzSort関数は、Perlのイディオムやdecorate-sort-undecorateイディオムよりも、より少ないテンポラリデータで、より高速に動作する。 Perlのイディオムや、PythonやLispにあるdecorate-sort-undecorateイディオムよりも高速かもしれない。 イディオムよりも速いかもしれない。これは、ソートがインプレースで行われるためである。 というのも、並べ替えはインプレースで行われ、最小限のデータ(変換された要素の配列1つ)しか生成されないからである。 生成されるからだ。

配列がソートされたかどうかをチェックし、シュワルツ・ソートの高速化の恩恵を受けるために、。 を呼び出すことで実現できるため、schwartzIsSorted 関数は提供されない。 isSorted!less(map!transform(r))を呼び出すことで実現できるからである。

Parameters:

transform	適用する変換。単項関数( )または二項関数のいずれかである。 (unaryFun!transform(element))、またはバイナリ関数 (binaryFun!transform(element, index)) のいずれかである。
less	変換された要素をソートする述語。
ss	使用するスワッピング戦略。
R r	ソートする範囲。

Returns:

でSortedRange 。 (a, b) => binaryFun!less(transform(a), transform(b))でラップされる。

Examples:

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)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);

ランダムアクセスの範囲を並べ替える rを並べ替える。 r[0 .. mid] がソートされた場合と同じになるように、ランダムアクセスの範囲を並べ替える。 rがソートされた場合と同じになるように並べ替え 範囲を残す。 r[mid .. r.length]を残す。

pred をΟ(r.length * log(mid))評価する。 を呼び出すだけである。 topN!(less, ss)(r, n)sort!(less, ss)(r[0 .. n])を呼び出すだけである。

Parameters:

less	ソートする述語。
ss	使用するスワッピング戦略。
Range r	並べ替えるランダムアクセス範囲。
size_t n	ソートする rの最初のセグメントの長さ。

Examples:

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)
if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2);

左側の2つの範囲の最小の要素をソートして格納する。

Parameters:

less	ソートする述語。
ss	使用するスワッピング戦略。
Range1 r1	最初の範囲。
Range2 r2	2番目の範囲。

Examples:

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)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);

範囲を並べ替える rスワップ を使って並べ替える。 r[nth]が完全にソートされた場合にそこに入る要素を指すようにする。 が完全にソートされた場合にそこに入る要素を指すようにする。

これはQuickselectに似ている、 と似ており rからすべての要素 e1 から r[0]から r[nth]を満たすように分割する。 !less(r[nth], e1), を満たし、かつすべての要素e2 が r[nth]から r[r.length]を満たす。 !less(e2, r[nth]).を満たす nth + 1最小の less(の要素を見つける。 r.を実行する。 Ο(r.length) (不安定な場合) またはΟ(r.length * log(r.length)) を実行する。 less (安定している場合) の評価を行う。

もし n >= r.lengthの場合、アルゴリズムには何の効果もなく r[0 .. r.length].

Parameters:

less	ソートする述語。
ss	使用するスワッピング戦略。
Range r	並べ替えるランダムアクセス範囲。
size_t nth	関数が終了した後、ソートされた位置にあるべき要素のインデックス。 関数が終了した後にソートされた位置にあるべき要素のインデックス。

Returns:

から r[0]から r[nth]までのスライスである。 r[nth]を除く。

See Also:

topNIndex,

Bugs:

安定したtopNはまだ実装されていない。

Examples:

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)
if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2);

2つの範囲の最小要素を左側の範囲に格納する。

Parameters:

less	ソートする述語。
ss	使用するスワッピング戦略。
Range1 r1	最初の範囲。
Range2 r2	2番目の範囲。

Examples:

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)
if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);

入力範囲の上位n 要素をコピーする。 入力範囲sourceにコピーする。 にコピーする。 targetにコピーする。 n = target.length.

の要素は触れない。 sourceの要素はタッチされない。sorted がtrue の場合、ターゲットはソートされる。そうでない場合は はヒープ特性を尊重する。

Parameters:

less	ソートする述語。
SRange source	ソート元の範囲。
TRange target	ターゲット範囲。
SortOutput sorted	にコピーされた要素をソートするかどうか。 target.

Returns:

コピーされた要素を含む targetのスライスである。

Examples:

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)
if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex);

要素の範囲が与えられたとき、その上位n個の要素のインデックスを作成する。 (のインデックスを構築する。)

と似ている。 topNただし、範囲は変更されない。

Parameters:

less	範囲要素の順序を定義する二項述語。 デフォルトはa < b 。
ss	(まだ実装されていない。)スワッピング戦略を指定する。
Range r	A ランダムアクセス範囲 インデックスを作成する要素の範囲。
RangeIndex index	A ランダムアクセス範囲 で、インデックスを作成するために割り当て可能な要素を持つ。この範囲の長さ でインデックスを作成する先頭要素の数を決定する。 r. このインデックス範囲は、積分要素を持つことができる。 へのゼロベースの数値添字で構成される。 rへのポインターを持つこともできる。 rへのポインタを持つこともできる。 の先頭要素へのポインタとなる。 r.
SortOutput sorted	を参照する要素でインデックスをソートするかどうかを決定する。 でソートするかどうかを決定する。

See Also:

topN, topNCopy.

Bugs:

スワッピング戦略パラメーターはまだ実装されていない。 は無視される。

Examples:

import std.typecons : Yes;

// 数値インデックスを使用して、上位3要素へのインデックスを構築する:
int[] a = [ 10, 2, 7, 5, 8, 1 ];
int[] index = new int[3];
topNIndex(a, index, Yes.sortOutput);
assert(index == [5, 1, 3]); // なぜなら、a[5]==1、a[1]==2、a[3]==5

// ポインタインデックスを使用して、上位3要素へのインデックスを構築する:
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)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);

順列 rangeを、辞書的に次の順列に置き換える。 並べ替えを行う。

述語less は、その範囲で使われる辞書的順序を定義する。 を定義する。

範囲が現在辞書的に最大の順列である場合、それは最小の順列に戻され、falseが返される。 を返す。 そうでなければ が返される。このように、 に従ってソートすることで、範囲のすべての順列を生成することができる。 less に従ってソートする。 に従ってソートし、falseを返すまでnextPermutationを呼び出す。 これは、範囲のすべての異なる順列を生成することが保証されている。 を正確に1回生成することが保証される。 範囲にN個の要素があり、そのすべてが一意であれば、N! N個の順列が生成される。そうでない場合は の順列が生成されることになる。

// すべての順列を列挙する
int[] a = [1,2,3,4,5];
do
{
    // 現在の並べ替えを使用し、
    // 配列の次の並べ替えに進む。
} while (nextPermutation(a));

Parameters:

less	並べ替えの辞書的順序を決定するために使われる順序。 順列を決定するために使われる順序。
BidirectionalRange range	並べ替える範囲。

Returns:

その範囲が辞書的に最大であった場合は偽となる。 を返す。 を返す。

See Also:

std.algorithm.iteration.permutations.

Examples:

// ソートされた配列のすべての順列を辞書順にステップ実行する
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]

Examples:

// 重複要素を含む配列の順列をステップ実行する:
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)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);

パーミュート rangeを次の辞書的に大きな偶数順列に置き換える。 並べ替えを行う。

述語less は、その範囲で使われる辞書的順序を定義する。 を定義する。

偶数順列とは、元の範囲内の要素の組を偶数個入れ替えることによって生成されるものである。 のペアを入れ替えることによって生成されるものである。偶数順列の集合 の集合は、すべての順列の集合と区別される。 のみである。範囲にN個の一意な要素がある、 の偶数順列が存在する。

範囲がすでに辞書的に最大の偶数順列である場合、それは最小の偶数順列に戻され、偽が返される。 は最小の偶数順列に戻され、false が返される。 そうでない場合、true が返され、範囲はその場で修正される。 に変更される。

このようにして、一意な要素を持つ範囲の偶数順列を生成することができる。 を生成することができる。 nextEvenPermutationをfalseを返すまで繰り返し呼び出す。

// 偶数列の並べ替えを列挙する
int[] a = [1,2,3,4,5];
do
{
    // 現在の並べ替えを使用し、
    // 配列の次の偶数並べ替えに進む。
} while (nextEvenPermutation(a));

また、ある範囲の奇数の順列を生成することもできる。 順列は偶数＋偶数＝偶数、奇数＋偶数＝奇数という規則に従う。 したがって、辞書的に最小の範囲の最後の2つの要素を入れ替えると、最初の奇数の順列になる、 は最初の奇数順列になる。次に nextEvenPermutationを呼び出すと、この最初の奇数順列に対して次の偶数順列が生成される。 を生成する。 である。このように nextEvenPermutationをfalseを返すまで繰り返し呼び出すことで、元の範囲の奇数順列を列挙することができる。 を列挙することになる。

// 奇数の並べ替えを列挙する
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]);    // a は現在、[1,2,3,4,5]の最初の奇数順列である
do
{
    // 現在の並べ替えを使用し、
    // 元の配列の次の奇数並べ替え
    // (最初の奇数並べ替えの偶数並べ替え)に進む。
} while (nextEvenPermutation(a));

警告 偶数の順列はすべての順列と区別されるのは、範囲の要素が一意であるときだけである。 とは区別されないので、この関数は指定された順序で重複する要素がないと仮定する。 と仮定する。これが真でない場合 順列の生成に失敗することがある。範囲に一意でない 要素がある場合は nextPermutationを使わなければならない。

Parameters:

less	並べ替えの辞書的順序を決定するために使われる順序。 順列を決定するために使われる順序。
BidirectionalRange range	並べ替える範囲。

Returns:

その範囲が辞書的に最大であった場合は偽となる。 を返す。 を返す。

Examples:

// 辞書式順序でソートされた配列の偶数置換を順を追って実行する
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]

Examples:

順列でさえも、特定の幾何学的形状の座標を生成するのに役立つ。 の座標を生成するのに役立つ。以下はその例である:

import std.math.algebraic : 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)
{
    // 各シードの偶数順列をループする
    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));
}
writeln(n); // 60

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

パーマネント rangeを perm順列に変換する。

このアルゴリズムは、作成される順列の数に対して一定の実行複雑度を持つ。 である。 ulong の最初の21個の要素のみである。 rangeの最初の21要素のみが順列化される。したがって、残りの範囲は順列化されない。 である。 このアルゴリズムはLehmer コードを使用する。

アルゴリズムは以下のように動作する:

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

Returns:

順列の範囲である。

Parameters:

Range range	レンジを順列化する。元の順序は失われる。
ulong perm	並べ替える rangeを指定する。

Examples:

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)
if (isRandomAccessRange!Range && hasLength!Range);

Returns:

true 順列がうまくいった場合は、 。false permには は階乗の桁数がrangeの要素数より多かった。 このようなケースは範囲外アクセスにつながるため、発生させてはならない。

Examples:

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