ソート
ソート (テンプレート:En) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない[1]）
主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、テンプレート:En）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、テンプレート:En）という。
対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。
目次
概要
効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。
- 設定された順序（昇順または降順）に対して、逆になるような順序の出力があってはならない。
- 出力は入力の並べ替えでなければならない。
情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている[2]。多くの人は既に解決済みの問題と考えているが、現在も新たなソートアルゴリズムが発明されている（例えば、ライブラリソートが最初に発表されたのは2004年である）。様々なアルゴリズムがあり、アルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。
ソートアルゴリズムの分類
計算機科学では、ソートアルゴリズムを次のように分類する。
安定ソート
同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。
安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）
内部ソートと外部ソート
ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソートを内部ソートという。クイックソートのような再帰を利用するアルゴリズムは、再帰のために O(log n) の領域を必要とすることからIn-placeであるか否かは議論が分かれるところであるが、これも内部ソートに含めるのが一般的である。このことから内部ソートは、ソートされるデータの格納域以外には O(1) か O(log n) の領域しか必要としない。
逆に、ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソートという。
メモリ使用量（およびその他の計算資源の使用量）による分類である。すべての内部ソートは、インデックスや参照、複製を作成して処理することで事実上の外部ソートにすることができる。アルゴリズムとしての本質ではないので一般的には無視されるが、高速化や柔軟な処理のために冗長な記憶領域を使用する場合がある。例えば、非安定ソートアルゴリズムで安定ソートを実現する場合など。（→#安定ソート）
比較ソート
個々の項目を比較演算で大小判定することを基本とするソートを比較ソートという。
比較ソートには#比較ソートの理論限界が存在する。
計算量
入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n2) である。理想は O(n) である。
比較ソートでは、必ず O(n log n) の比較が必要となる。（→#比較ソートの理論限界）
手法
汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。
再帰
再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。
ソートアルゴリズムの一覧
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。 計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。
以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。
| 名称 |
平均計算時間 |
最悪計算時間 |
メモリ使用量 |
テンプレート:Nowrap |
手法 |
備考 |
|---|---|---|---|---|---|---|
| バブルソート | — | O(n2) | O(1) | ○ | 交換 | |
| シェーカーソート | — | O(n2) | O(1) | ○ | 交換 | |
| コムソート | O(n log n) | O(n2) | O(1) | × | 交換 | コードサイズが小さくて済む。 |
| ノームソート | — | O(n2) | O(1) | ○ | 交換 | |
| テンプレート:Display none選択ソート | O(n2) | O(n2) | O(1) | × | 選択 | 安定ソートとしても実装可能 |
| テンプレート:Display none挿入ソート | O(n + d) | O(n2) | O(1) | ○ | 挿入 | d は置換群の反転数で、テンプレート:Nowrap |
| シェルソート | — | O(n log2 n) | O(1) | × | 挿入 | |
| 2分木ソート | O(n log n) | O(n log n) | O(n) | ○ | 挿入 | 平衡2分探索木を使った場合 |
| ライブラリソート | O(n log n) | O(n2) | O(n) | ○ | 挿入 | |
| マージソート | O(n log n) | O(n log n) | O(n) | ○ | マージ | |
| In-place マージソート | O(n log n) | O(n log n) | O(1) | ○ | マージ | 実装例 |
| ヒープソート | O(n log n) | O(n log n) | O(1) | × | 選択 | |
| スムースソート | — | O(n log n) | O(1) | × | 選択 | |
| クイックソート | O(n log n) | O(n2) | O(log n) | × | テンプレート:Nowrapョニング | 単純な実装ではメモリ使用量が テンプレート:Nowrap になる。 ピボット値として中央値を使えば、最悪時間が テンプレート:Nowrap |
| イントロソート | O(n log n) | O(n log n) | O(log n) | × | 混成 | STLの実装によく使われている。テンプレート:要出典 |
| ペイシェンスソート | — | O(n2) | O(n) | × | 挿入 | テンプレート:Nowrapにすべての最長増加部分列を探す。 |
| ストランドソート | O(n log n) | O(n2) | O(n) | ○ | 選択 | |
| テンプレート:Display none奇偶転置ソート | — | O(n2) | O(1) | ○ | 交換 | |
| シェアソート | — | O(n1.5) | O(1) | × | 交換 |
次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2k を仮定している（<< は「十分小さい」）。
| 名称 |
平均計算時間 |
最悪計算時間 |
メモリ使用量 |
テンプレート:Nowrap |
n << 2k? |
備考 |
|---|---|---|---|---|---|---|
| テンプレート:Display none鳩の巣ソート | O(n+2k) | O(n+2k) | O(2k) | ○ | ○ | |
| バケットソート | O(nk) | O(n2k) | O(nk) | ○ | × | テンプレート:Nowrap定義域に一様分布すると仮定 |
| テンプレート:Display none分布数えソート | O(n+2k) | O(n+2k) | O(n+2k) | ○ | ○ | |
| LSD 基数ソート | O(nk/s) | O(nk/s) | O(n) | ○ | × | |
| MSD 基数ソート | O(nk/s) | O(n (k/s) 2s) | O((k/s) 2s) | × | × | |
| スプレッドソート | O(nk/log (n)) | O(n (k - log (n))0.5) | O(n) | × | × | テンプレート:Nowrap の場合の計算時間だが、それ以外の場合でもソート可能 |
| テンプレート:Display none逆写像ソート | O(n) ? | N/A | O(n) ? | ○ | × |
次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。
| 名称 |
平均計算時間 |
最悪計算時間 |
メモリ使用量 |
テンプレート:Nowrap |
大小比較 |
備考 |
|---|---|---|---|---|---|---|
| ボゴソート | O(n × n!) | ∞ | O(1) | × | ○ | 平均時間はクヌースのシャッフルを使った場合 |
| ボゾソート | O(n × n!) | ∞ | O(1) | × | ○ | 平均時間はボゴソートの約半分に漸近する。 |
| ストゥージソート | O(n2.71) | O(n2.71) | O(log n) | × | ○ | |
| ビードソート | N/A | N/A | — | N/A | × | 専用ハードウェアが必要 |
| テンプレート:Display none単純パンケーキソート | O(n) | O(n) | O(log n) | × | ○ | 反転を定数時間で行えるものと仮定 |
| ソーティングネットワーク | O(log n) | O(log n) | O(n log n) | ○ | × | テンプレート:Nowrap の回路が必要 |
比較ソートの理論限界
計算理論において、n個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でも O(n log n) 必要なことが知られている。O(n) で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意を要する。
最悪計算量が最低でもO(n log n) 必要である略証を示す。
ソーティングはデータの並べ替えである。 n個のデータの並べ替えは置換を用いて書け、置換はn!個ある。 スターリングの公式より、n!= O(nn) 。
プログラム中の分岐はif文でしか起こらない。 1回のif文でプログラム中は2つに分岐するので、 n!個の置換をすべて実現する必要なif分岐の個数をmとすると、 2m ≧ n!= O(nn) でなければならない。 したがって、ソーティングの最悪計算量は最低でも m = O(n log n) である。
メモリ使用パターンとインデックスソート
ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。
例えば、再帰型のクイックソートは主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。
対策の一つとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある[3]。
別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。
これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。
脚注・出典
参考文献
- D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.
関連項目
外部リンク
- Sequential and parallel sorting algorithms - 各種アルゴリズムの説明と解析
- Ricardo Baeza-Yates' sorting algorithms on the Web
- 'Dictionary of Algorithms, Data Structures, and Problems'
- Slightly Skeptical View on Sorting Algorithms Softpanorama。古典的アルゴリズムについて論じ、クイックソートの代替となるアルゴリズムを提案。
- Sorting Revisited
- The Stony Brook Algorithm Repository コード例と解説
ソートアルゴリズムの視覚化
- graphical demonstration ボストンカレッジ。8種類のソートアルゴリズムに4種類の典型的な初期条件を与えたときのソートの様子をグラフィカルに表示している。
- graphical demonstration リンショーピング大学
- sort algorithm visualizer 11種類のソートアルゴリズムについて各種初期条件でのソートの様子を視覚化
- いくつかのソートアルゴリズムを視覚化したJava applet
- Sort Animation Javaアプレットによるバブルソート、挿入ソート、クイックソート、選択ソートのアニメーション図解
- xSortLab - 別のJavaアプレット。バブルソート、挿入ソート、クイックソート、選択ソート、マージソートをアニメーション化している。ソート対象を縦の棒で示している。
- Sorting contest - 8種類のソートアルゴリズムのアニメーションを一斉に実行でき、速度の違いを体感できる。
- ↑ パンチカードシステムの時代には、下位の桁から順に分類しては併合することがまさしく整列であった（O(n) のバケットソートになる）。
- ↑ Bubble Sort: An Archaeological Algorithmic Analysis Owen Astrachan
- ↑ tag sort Definition PCMAG.COM
