ソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ソート（sort）は、データの集合を一定の規則に従って並べることである。日本語では整列（せいれつ）と訳される。（以前は分類と訳していた時もあったが、この訳は間違いであり、もう使われていない。）
主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係を定義して一列に並べることを指す。また、単に「ソート」といった場合、値の小さい順に並べる昇順（しょうじゅん／ascending order）を指すことが多い。また、その反対に値を大きい順から並べることを降順（こうじゅん／descending order）という。
対象となるデータのデータ構造や、必要な出力によって使われるアルゴリズムは異なる。
目次 |
[編集] 概要
効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。
情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている[1]。多くの人は既に解決済みの問題と考えているが、現在も新たなソートアルゴリズムが発明されている（例えば、ライブラリソートが最初に発表されたのは2004年である）。様々なアルゴリズムがあり、アルゴリズムという概念を学習するのに最適であるため、情報工学や計算機科学での入門的題材として広く親しまれている。それには例えば、O記法、分割統治法、データ構造、乱択アルゴリズム、計算量解析、時間と空間のトレードオフ、下限などが含まれる。
[編集] ソートアルゴリズムの分類
計算機科学では、ソートアルゴリズムを次のように分類する。
- 入力されるリストの項目数（n）に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n)、最悪で Ω(n2) である。理想は O(n) である。抽象キーの比較演算のみを使うソートアルゴリズムでは、最悪で Ω(n log n) の比較が必要となる。
- In-placeアルゴリズムの場合、スワップ回数で計算量を求め、それによって分類する。
- メモリ使用量（およびその他の計算資源の使用量）による分類。一部のソートアルゴリズムはIn-placeであるため、入力リストの格納域以外には O(1) または O(log n) の領域しか必要としない。これを内部ソートと呼ぶ。一方、他のアルゴリズムではデータを一時的に記憶しておく領域が必要である。これを外部ソートと呼ぶ。
- 再帰の有無による分類。一部のアルゴリズムは再帰が必須だったり、再帰不可能だったりするが、それ以外はどちらでも実装可能である（例えばマージソート）。
- 安定性の有無。安定ソート参照。
- 比較ソートか否か。比較ソートでは、2つの個々の項目を比較演算で大小判定することを基本とする。比較ソートには後述する理論限界が存在する。
- 汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやクイックソートが含まれる。選択ソートにはシェーカーソートやヒープソートが含まれる。
[編集] ソートアルゴリズムの一覧
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。 計算時間の表記に用いている記号 O についてはランダウの記号を参照。
以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。
| 名称 | 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 | 手法 | 備考 |
|---|---|---|---|---|---|---|
| バブルソート | — | O(n2) | O(1) | ○ | 交換 | |
| シェーカーソート | — | O(n2) | O(1) | ○ | 交換 | |
| コムソート | O(n log n) | O(n log n) | O(1) | × | 交換 | コードサイズが小さくて済む。 |
| ノームソート | — | O(n2) | O(1) | ○ | 交換 | |
| 選択ソート | O(n2) | O(n2) | O(1) | × | 選択 | 安定ソートとしても実装可能 |
| 挿入ソート | O(n + d) | O(n2) | O(1) | ○ | 挿入 | d は置換群の反転数で、O(n2) |
| シェルソート | — | 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) | ○ | マージ | 実装例はこちら: [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) | × | パーティショニング | 単純な実装ではメモリ使用量が O(n) になる。 ピボット値として中央値を使えば、最悪時間が O(n log n) |
| イントロソート | O(n log n) | O(n log n) | O(log n) | × | 混成 | STLの実装によく使われている。[要出典] |
| ペイシェンスソート | — | O(n2) | O(n) | × | 挿入 | O(n log n) 以内に全ての最長増加部分列を探す。 |
| ストランドソート | O(n log n) | O(n2) | O(n) | ○ | 選択 | |
| 奇偶転置ソート | — | O(n2) | O(1) | ○ | 交換 | |
| シェアソート | — | O(n1.5) | O(1) | × | 交換 |
次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーサイズが十分大きく、各要素のキーが重複しないことを前提としている。すなわち、n << 2k を仮定している（<< は「十分小さい」）。
| 名称 | 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 | n << 2k? | 備考 |
|---|---|---|---|---|---|---|
| 鳩の巣ソート | O(n+2k) | O(n+2k) | O(2k) | ○ | ○ | |
| バケットソート | O(n·k) | O(n2·k) | O(n·k) | ○ | × | 入力データは定義域に一様分布すると仮定 |
| 分布数えソート | O(n+2k) | O(n+2k) | O(n+2k) | ○ | ○ | |
| LSD 基数ソート | O(n·k/s) | O(n·k/s) | O(n) | ○ | × | |
| MSD 基数ソート | O(n·k/s) | O(n·(k/s)·2s) | O((k/s)·2s) | × | × | |
| スプレッドソート | O(n·k/log(n)) | O(n·(k - log(n)).5) | O(n) | × | × | n << 2k の場合の計算時間だが、それ以外の場合でもソート可能 |
| 逆写像ソート | O(n)? | N/A | O(n)? | ○ | × |
次の表は、あまりにも性能が悪いため通常は使われないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。
| 名称 | 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 | 大小比較 | 備考 |
|---|---|---|---|---|---|---|
| ボゴソート | 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 | × | 専用ハードウェアが必要 |
| 単純パンケーキソート | O(n) | O(n) | O(log n) | × | ○ | 反転を定数時間で行えるものと仮定 |
| ソーティングネットワーク | O(log n) | O(log n) | O(n•log n) | ○ | × | 大きさ O(n•log n) の回路が必要 |
[編集] 比較ソートの理論限界
計算理論において、n個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でもO(n log n)必要なことが知られている。O(n)で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意されたい。
最悪計算量が最低でもO(n log n)必要である略証を述べる。
ソーティングはデータの並べ替えである。 n個のデータの並べ替えは置換を用いて書け、置換はn!個ある。 スターリングの公式より、n!=O(nn)。
プログラム中の分岐はif文でしか起こらない。 一回のif文でプログラム中は2つに分岐するので、 n!個の置換を全て実現する必要なif分岐の個数をmとすると、 2m≧n!= O(nn)でなければならない。 よってソーティングの最悪計算量は最低でもm = O(n log n)である。
[編集] メモリ使用パターンとインデックスソート
ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるため、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上で全てソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。従って、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。
例えば、再帰型のクイックソートは主記憶上では良い性能だが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。従って、そのような場合は比較回数が多くても他のアルゴリズムを使った方が良い。
対策のひとつとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある[2]。
別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。
これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。
[編集] 関連項目
[編集] 脚注・出典
- ^ Bubble Sort: An Archaeological Algorithmic Analysis Owen Astrachan
- ^ tag sort Definition PCMAG.COM
[編集] 参考文献
- 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種類のソートアルゴリズムのアニメーションを一斉に実行でき、速度の違いを体感できる。
