はじめに
データ構造とアルゴリズムのアドベントカレンダーということで、ちょっと珍しいと思ったソートアルゴリズムの実装を調べたので宣伝半分に書き残したいと思います。
（他のアルゴリズムが非常に高度なものばかりなので、書いてて不安がいっぱいです）
日頃主にD言語でお手軽ツールを書いたりしているのですが、今回のお題はD言語の標準ライブラリにある、その名も completeSort という関数の内部で使われているアルゴリズムです。
リファレンス : https://dlang.org/phobos/std_algorithm_sorting.html#completeSort
ソース : https://github.com/dlang/phobos/blob/master/std/algorithm/sorting.d#L115
ちなみに作者はリファレンスにもある通り、C++の大家で計算機科学の論文も多く執筆している Andrei Alexandrescu 氏です。
概要
これがどんなソートアルゴリズムか先に言ってしまうと、「データの先頭部分がソート済みという条件下で、残りの部分を1つずつ前半に対する二分探索で挿入していく」という動きをするソートアルゴリズムです。
雑に言えば、二分探索有りの挿入ソートをちょっと進めたところから再開する、という感じでしょうか。
前提となるデータを形式的に書くと以下のようになります。
- 要素数 $n$ で $[x_0, x_1, ..., x_{n-1}]$ というデータをソートする
- このデータのうち、 $0 < m < n$ である $m$ に対して $[x_0, x_1, ..., x_m]$ がソート済みとする
- $[x_{m+1}, ..., x_{n-1}]$ の値は不問（$[x_0, ..., x_m]$ の値より大きくても小さくても良い）
これに対してソートの平均計算量が $\mathcal{O}(m + (n - m) * log (n - m))$ 、最悪計算量は $\mathcal{O}(n * log(n))$ となります。（リファレンスより）（なんか違う気もしている）
良いところ
何といっても、**「データの大部分がソート済みの場合（ $n-m$ が小さい場合）に計算量がとても少ない」**に尽きます。
状況次第では通常のクイックソートやイントロソートより速い場合が多いです。
これが活きるのはどんな状況か？
私は遺伝的アルゴリズムの実装で使いました。
遺伝的アルゴリズムの詳細は世の公開資料にお任せしますが、ざっくりいうと生物の進化や遺伝の過程を模倣して、以下のステップを繰り返し、たくさんの個体からスコアの高い個体を作り出す、というものです。
- たくさんの個体を用意して、それぞれを評価してスコアを付ける
- 評価した個体を混ぜたりして新しい個体を一定数作る（交叉・変異）
- 作った個体も評価してスコアを付ける
- 元の個体と作った個体の中から次の世代の一覧を作って2に戻る（選択）
この4で次の世代を作るときに一度スコア順にソートするので、「元々ある現世代の個体一覧は前ステップでソート済み」という条件から、うまいことするとこのアルゴリズムがジャストフィットします。
ちなみに手元では、現世代の数を $N$ 、新世代の数を $M$ としたとき、 $M = 2 * N$ くらいで実験していました。ざっくり3分の1がソート済みということになります。
$N=100,1000,10000,100000$ くらいで色々個体数を変えて実験しましたが、標準のソート（イントロソート）と比べて26%ほど高速化されたのでやったぜ、という感じです。
似たようなケースに対して、ソートが高速化できるような例をご存知の方がいればぜひ教えてください！
プログラム例
実際この例をD言語で書いてみると以下のような感じです。
大体C++とJavaとC#を足して3で割った感じだと思って見てみてください。
オンライン実行例 : https://run.dlang.io/is/JwBz5K
import std.stdio;
import std.algorithm;
import std.range;
// 先頭3要素はソート済みの想定
int[] a = [1, 2, 3, 5, 0, 10, -3, 6, 4];
completeSort(a[0 .. 3].assumeSorted(), a[3 .. $]);
writeln(a);
[-3, 0, 1, 2, 3, 4, 5, 6, 10]
まとめ
というわけで、いつも使っている言語でも標準ライブラリを漁ってみると思わぬアルゴリズムに出会うことがある、というお話の記録でした。
みなさんもぜひ日ごろ使っている言語の標準ライブラリを眺めてみたりして、身近にある面白いアルゴリズムを探してみてください！