最悪計算時間、平均計算時間や安定なソート、不安定なソートなんかの話が出てきますよね。簡単なアルゴリズムの例としてバブルソートや選択ソート、挿入ソートなどが出てきて、そのあとに高速なアルゴリズムとしてクイックソートやマージソートが出てくると思います。
さて、それではソートのスピードに限界はあるのでしょうか。
計算時間の"オーダー"
その前に復習です。よく「計算時間のオーダー」というものが言われますね。話を厳密にするために定義しておきましょう。ビッグオー記法
定義：ある関数$f(n)$に対して定数$a$,$c$が存在し、すべての$n>a$に対して$f(n) \leq c \cdot g(n)$を満たすとき、$f(n)=O(g(n))$と書く。これがいわゆるオーダーと呼ばれるものです。どんな$a$を取ってきても、それより大きな$n$だったら必ず$f(n)$は$g(n)$の定数倍より小さくなる、ということを言っています。$n$が無限まで行っても必ず$g(n)$の定数倍にはかなわないため、最も大きくなるパターンを想定するうえで非常に有用です。
ビッグオメガ記法
定義：ある関数$f(n)$に対して定数$a$,$c$が存在し、すべての$n>a$に対して$f(n) \geq c \cdot g(n)$を満たすとき、$f(n)= \Omega (g(n))$と書く。オーダーよりもちょっとマイナーな記法だと思います。ビッグオー記法との違いは不等号です。どんな$a$を取ってきても、それより大きな$n$だったら必ず$f(n)$は$g(n)$の定数倍より大きくなる、ということを言っています。こちらは逆に最も小さくなるパターンを想定する上で有用です。
これらの定義は一般化して数学的に厳密に行ったものです。アルゴリズムの良さの尺度として用いるときは、$n$はたいてい配列長とします。配列長が長くなるとソートにかかる時間$f(n)$がどうなるのか、というのが最も評価すべき指標だからです。
細かな話をすればそれ以外の評価指標もあるのですが、まずはここから入ります。
注意事項
1. 定数倍までは気にしない
これらの指標は定数倍の違いは許容しています。これは、あくまでも$n$に対する相関を考えているためです。ですので、同じオーダーでも計算時間が平気で2倍3倍、極端な話10倍100倍違うこともあり得ます。そんなの困るじゃないかと思うかもしれませんが、逆に言えば、オーダーが同じアルゴリズムでは$n$がどんなに増えても高々定数倍しか計算時間は変わらないということになります。オーダーが変わると定数倍よりも大きな計算時間の差が出るため、それに比べれば高々定数倍しか差が出ないのは、アルゴリズムの良し悪しを検討する上では些細な問題なのです。逆に言えば、その些細な問題を気にするようなステージでは、この記事の議論は的外れであるという認識を持っていただいて構いません。
2. タイトな表現をすること
上記の定義に従えば、例えば$O(n^2)$のところを$O(n^{100})$と書いても間違いではありません。ですが、評価指標としては役に立たないものになってしまいます。ですので、特別な要求が無い限りは最もタイトな表現をすることとします。タイトな表現とは、あるアルゴリズムについて$O(f(n))$と$O(g(n))$という2通りの書き方があったとき、$f(n)=O(g(n))$かつ$g(n) \neq O(f(n))$であるとき、$f(n)$のほうがよりタイトな表現と定義することができます。
比較ソートの理論限界
さて、種々の定義が終わったところで本題に移っていきます。クイックソートとマージソートは高速で、平均計算時間は$O(n \log n)$だという認識を持っている人は多いと思います。
ではソートはこれ以上速くなることができるのでしょうか。
実は、大小比較に基づいたソートには理論限界があります。
比較とは、配列の中の2つの要素$a$,$b$を取り出して、$a \leq b$か$a>b$かを判定する作業のことを言います。
比較を1回行うと、「以上」か「未満」の2通りの答えが出てくるため、内容によって配列の並べ方が2通りに分岐します。そこからもう1回比較をするとさらに2通りに分岐するため、$t$回の比較では$2^t$種類の並べ方に分類することができます。
一方、ソートとはいくつもある並び替え方の中から唯一の並び方を決定する作業だと言いかえることができます。$n$個の要素の並び替え方は$n!$通りありますので、以下の式が成り立ちます。\[
2^t \geq n!
\]いくつもある並べ方の中から1つの並べ方を特定するには、すべての並べ方をカバーできるだけの比較はしておかなければなりません。逆に言えば（と言うよりか対偶に言えば）、すべての並べ方をカバーできない回数の比較では、1つの並べ方を特定することができません。なのでこの式が成り立つわけです。
ここからの式変形はスターリングの公式を使うとした文献が多いですが、実はそんなに大した計算ではないので自力で解いてみましょう。\[\begin{align*}
2^t &\geq n!\\
t &\geq \log n!\\
&\geq \sum_{k=1}^{n} \log k > \int_1^{n} \log x \mathrm{d}x
\end{align*}\]最後の不等式は面積を考えれば一発ですね。
\[\begin{align*}
\int \log x \mathrm{d}x &= x \log x - \log e \int x \cdot \frac{1}{x}\mathrm{d}x\\
&= x \log x - x \log e+C
\end{align*}\]\[
\therefore t>n \log n+(1- n) \log e =O(n \log n)
\]logの積分とか懐かしいですね。ただ、logは底が2なので積分時には注意する必要があります。
これによって、比較に基づいたソートである限り、最悪計算時間は$\Omega (n \log n)$であることがわかりました。クイックソートやマージソートは、オーダーの上では理論上最速なのです。
比較に基づかないソート
さて、前節でわざわざ比較に基づいたソートと書いたからには、比較に基づかないソートも存在するわけです。そうすれば、$O(n \log n)$を割り込むかもしれません。バケットソート
配列は任意の要素を$O(1)$の計算時間で読み書きできます。ですので、並び替えたい数列の要素が0以上の整数で上限がわかっている場合、0～上限までの長さの配列を用意することで数列に含まれるすべての整数の個数を$O(n)$で数えきることができます。すべての個数がわかれば、小さいほうから順にその整数をその個数入れていけばソートの完成です。const int max = 10;
Random rnd = new Random();
int[] array = new int[100];
//乱数を準備（値は0～9）
for(int i = 0; i < array.Length; i++)
array[i] = rnd.Next(10);
Console.WriteLine("Before:");
Console.WriteLine(string.Join(", ", array));
//バケットソート
int[] result = new int[max];
for(int i = 0; i < array.Length; i++)
result[array[i]]++; //個数をカウントする
int pos = 0;
for(int i = 0; i < max; i++) {
for(int j = 0; j < result[i]; j++)
array[pos++] = i; //個数分だけその数を入れる
}
Console.WriteLine("After:");
Console.WriteLine(string.Join(", ", array));
ただ、これの欠点は0以上の整数にしか使えないことで、さらに0～上限までのメモリが必要になります。上のサンプルコードでは上限を9としたので大したことありませんが、例えば32bit整数だったら4GiBのメモリが必要になってきます。実用上かなり不便です。
鳩ノ巣ソート
上記のバケットソートは数字の数を数えているだけですので、数字以外のソートには使えません。数字を付帯する何かしらのデータ（例えばファイルサイズを持っているファイル情報データ）をソートしたい場合に一工夫必要です。そこで、ソートしたい整数に対応した配列の各要素として今度はこのデータを収める配列をそれぞれ確保すればバケットソートを適用できます。これを鳩ノ巣ソートと呼びます。
この時、必要なメモリは、並び替えたい整数の種類$k$と配列長$n$を使って$kn$と表せます。例えば32bit数値のデータ1024個を並び替えたければ4TiBのメモリが必要になります。もはやアホくさいレベルです。
（並び替えるデータを片方向連結リストとすることでバケットソートレベルまで使用するメモリを減らせます。が、まだまだ非現実なレベルです。）
基数ソート
バケットソートや鳩ノ巣ソートではとてつもない大きさのメモリが必要になるので、その作業を何回かに分けてメモリの使用量を抑えたのが基数ソートになります。まず1の位だけを見て鳩ノ巣ソートを行います。この時、10進数ならば取り得る数字は10種類だけなのでメモリ量も配列長の10倍ほどで済みます。
次は、並び替え終わったデータに対して今度は10の位で鳩ノ巣ソートを行います。安定なソート前提だと、10の位がソートされ、同じ10の位については1の位がソートされた状態になります。すなわち下2桁がソートし終わったことになります。
次は100の位、1000の位と同様の処理をしていきます。最大桁数まで処理を終えたら終了です。
コンピューターは通常8bit単位でデータを扱いますので、256進数とみなして基数ソートを行えば、例えば32bit値ならば4回のループで計算が終わります。鳩ノ巣ソートと同様、片方向連結リストを使うことでメモリの使用量もそこそこ抑えることができます。
スリープソート
いつもネタ枠扱いされていますが、これも立派な非比較ソートです。並び替えたい配列の各要素に対して、例えばその数×1ミリ秒待つタイマーを一斉にスタートさせ、タイマーが鳴ったものから順に結果を格納していけばソートが完了するというものです。
バケットソート、鳩ノ巣ソート、基数ソートは整数しかソートできませんでしたが、時間は配列と違って連続ですので、スリープソートは小数に対しても行うことができます。すごい！！
ただ、これを現代の一般的なコンピューターにやらせようとすると、実際は中には1つのストップウォッチのみが入っていて、タイマー時間をもとに数字を並び替えて、小さいほうから順に鳴らしていくということになってしまいます。スリープソートをしたつもりで裏でOSが別の手法でこっそりソートをしているんですね。
また、「一斉にタイマーをスタートさせる」というのも一般的なコンピューターでは現実的に難しく、 スタートのタイミングの誤差だったり、もしくはスレッド切替時の誤差で正確なソートができなくなってしまうこともあります。
そういった点からいつもネタ扱いされていますが、私個人としては、バケットソートをメモリ空間軸上から時間軸上に動かして考案された、なかなか面白いアイディアだと思っています。
現実を見ていないソートアルゴリズムなのではない、現実が追い付いていないだけなのだ。
計算時間の比較
実際にマージソートと基数ソートを実装し、計算時間を比較してみました。お約束ですが、実装や環境で速度そのものについては変わってくると思います。ただ、オーダーについての考え方は同じはずですので、その着眼点で見てください。
マージソートの$O(n \log n)$の見た目が$O(n)$とほとんど変わらないのでパッと見ではわかりませんが、近似直線を引くと確かに直線より上側に沿っている（2階微分が正）のがわかります。
一方で基数ソートのほうは近似直線に沿っています。確かに$O(n)$です。
おまけですが、これの原点付近を拡大するとこうなります。
配列長が200前後でマージソートと基数ソートの計算時間が逆転しています。
これがオーダーの威力です。配列長が小さいと実装の差が出てきますが、配列長が大きくなるとオーダーが圧倒的な支配力を持ってきます。ですので、まずはオーダーの小さなソート手法を確立するのが先決なのです。
