ソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ソートは、データの集合を一定の規則に従って並べること。日本語では整列という。以前は分類と訳していた時もあったが、この訳は間違いであり、もう使われていない。
ほとんどの場合、データに関して全順序関係を定義して一列に並べることを指す。また、単に「ソート」といった場合、昇順に並べることを指すことが多い。
対象となるデータのデータ構造や、必要な出力によって使われるアルゴリズムは異なる。
ソートの際、定数個より多くの外部記憶領域を必要とするソート法の事を外部ソートといい、そうでないソート法を内部ソートという。
目次 |
[編集] ソートアルゴリズム
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。 計算時間の表記に用いている記号 O についてはランダウの記号を参照。
| ソート法 | 平均計算時間 | 安定ソート | 外部記憶 |
|---|---|---|---|
| バブルソート | O(n2) | ○ | O(1) |
| シェーカーソート | O(n2) | ○ | O(1) |
| コムソート | O(n log n) | × | O(1) |
| 選択ソート | O(n2) | × | O(1) |
| 挿入ソート | O(n2) | ○ | O(1) |
| シェルソート | O(n1.25) | × | O(1) |
| ヒープソート | O(n log n) | × | O(1) |
| マージソート | O(n log n) | ○ | O(n) |
| クイックソート | O(n log n) | × | O(1) |
| バケットソート | O(n) | ○ | O(n) |
| 基数ソート | O(n) | ○ | O(n) |
| 逆写像ソート | O(n) | ○ | O(n) |
| ボゴソート | O(n×n!) | × | O(1) |
[編集] 理論限界
計算理論において、n個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でもO(n log n)必要なことが知られている。O(n)で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意されたい。
[編集] 略証
最悪計算量が最低でもO(n log n)必要である略証を述べる。
ソーティングはデータの並べ替えである。 n個のデータの並べ替えは置換を用いて書け、置換はn!個ある。
プログラム中の分岐はif文でしか起こらない。 一回のif文でプログラム中は2つに分岐するので、 n!個の置換を全て実現する必要なif分岐の個数をmとすると、 
でなければならない。 よってソーティングの最悪計算量は最低でも
である。
