比較ソートアルゴリズムの時間複雑度
定理
$n$個のデータが与えられたとき、比較ソートアルゴリズムの時間計算量は以下の通りです。
- [1] バブルソート： $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
- [2] 選択ソート： $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
- [3] 挿入ソート： $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
- [4] ヒープソート： $$ \Theta ( n \log n ) \\ O ( n \log n ) $$
- [5] マージソート： $$ \Theta ( n \log n ) \\ O ( n \log n ) $$
- [6] クイックソート： $$ \Theta ( n \log n ) \\ O ( n^2 ) $$
説明
ここで紹介されるアルゴリズムの原理については一つ一つ説明しない。原理と実装自体をうまく説明している文書がたくさんあるし、生さえび寿司店が重要視する観点はそれらとはかなり離れているからだ。
ソートアルゴリズムはほとんど全てのプログラミングで動員されるが、「単純に実装されるだけ」や「一般的に最も優れたアルゴリズムを信頼する」だけでは文字通りの「最適化」ができない。見ての通り、単純なソートアルゴリズムは成功してもあまりにも多くの時間を無駄にするが、特定の条件下ではより複雑なアルゴリズムよりも高いパフォーマンスを出せるという事実を知る必要がある。こうした違いを明確に理解し、適切な場所にアルゴリズムを使うことがプログラマーの役割だ。
[1] バブルソート
GIFで確認できるように、水面下の泡が浮かぶような形から付けられた名前だ。時間計算量の面で比較ソートアルゴリズムの中で最も劣っているが、コード実装が非常にシンプルで、パッケージや内部関数に頼れないほど不利な環境でもすぐに書いて使える。
[2] 選択ソート
未ソートの領域から最大の数を一つだけ動かす方法なので、全データを覚える以外、最大の数を一つだけ覚えておけば十分だ。時間計算量の面では劣るが、空間計算量の面では非常に優れている。
[3] 挿入ソート
配列から一つずつ取り出して($n$回)、新しい配列のどこに入るべきかを見つけて($n$回)挿入するアルゴリズムなので、$O(n^2)$というのは事実だが、配列がほぼ整っている場合は新しい位置を探す手間がいらないので、ほぼ$\Theta ( n)$の時間がかかるかもしれない。実際のプログラミングで「配列がほぼ整っている」とは、配列のサイズが小さい状況を意味する。例えば、$n < 20$ほど小さいなら、たまたま配列がほぼ整っている状況がしばしば出ることがある。
[4] ヒープソート
ヒープデータ構造を利用した方法で、ヒープが構成されていれば$O ( \log n )$の時間だけでソートができる。ヒープを構成するには$O( n)$の時間が必要だが、これを考慮しても[1]～[3]と比べて非常に速い。ヒープソートが特に有利な部分は、ソートを一度に処理しない状況だ。ヒープソーティングで最も時間を多く消費するのはヒープを構成する段階だが、データが少しずつ追加されるなら、すでに構成されたヒープを修復することは大きな負担ではなく、ヒープが構成されていればソーティング自体は非常に速い。
[5] マージソート
フォン・ノイマンによって開発されたアルゴリズムで、時間計算量が$O ( n \log n )$で非常に速いだけでなく、同じ値の要素の順序がアルゴリズムを通過した後も維持される安定ソートアルゴリズムに属する。簡単に言うと、$(1, 3_{2}, 2, 3_{1}, 5)$があれば$(1, 2, 3_{2}, 3_{1}, 5)$のように$3_{2}$、$3_{1}$の順序が維持されるということだ。一次元配列ではこれは何の役にも立たないかもしれないが、何か代表値でソートする必要があるデータテーブルがあれば、この安定性が必要になる。$3_{2}$、$3_{1}$自体の順序はどうでもいいが、それらが持っているデータは何か意味のある順序で並べられている可能性があるためだ。
[6] クイックソート
クイックソートの最大の利点は、名前が示す通り、その速さだ。理論的には$O( n^2)$であり、ヒープソートやマージソートより劣っているし、$\Theta ( n \log n )$も利点として挙げる価値がないように見えるかもしれないが、実際に使うときはほぼ全ての場合で優れたパフォーマンスを示す。先に言及した「一般的に最も優れたアルゴリズム」とは、このクイックソートのことを指す。同様に、先に言及した他のソートアルゴリズムの特徴を理解していれば、クイックソートを主に使用しながらも、賢く他のアルゴリズムを選択できるだろう。