Dtyjlui

ウィキペディアの表のソートについては「Help:表の作り方#再整列可能な表」をご覧ください。

この項目では、整列について説明しています。16世紀スペインの神学者については「ドミンゴ・デ・ソト」をご覧ください。

ソート (sort) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていた)^[1]）

主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、descending order）という。

対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。

概要

効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の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(n²) である。理想は O(n) である。

比較ソートでは、必ず O(n log n) の比較が必要となる。（→#比較ソートの理論限界）

手法

汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。

再帰

再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。

ソートアルゴリズムの一覧

配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。
計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。

以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	手法	備考
バブルソート	—	$n^{2}$	$1$	○	交換
シェーカーソート	—	$n^{2}$	$1$	○	交換
コムソート	${displaystyle nlog n}$	$n^{2}$	$1$	×	交換	コードサイズが小さくて済む。
ノームソート	—	$n^{2}$	$1$	○	交換
センタク/選択ソート	$n^{2}$	$n^{2}$	$1$	×	選択	安定ソートとしても実装可能
ソウニユウ/挿入ソート	${displaystyle n+d}$	$n^{2}$	$1$	○	挿入	d は置換群の反転数で、 $O(n^{2})$
シェルソート	—	${displaystyle nlog ^{2}n}$	$1$	×	挿入
2分木ソート	${displaystyle nlog n}$	${displaystyle nlog n}$	$n$	○	挿入	平衡2分探索木を使った場合
図書館ソート	${displaystyle nlog n}$	$n^{2}$	$n$	○	挿入
マージソート	${displaystyle nlog n}$	${displaystyle nlog n}$	$n$	○	マージ
In-place マージソート	${displaystyle nlog ^{2}n}$	${displaystyle nlog ^{2}n}$	$1$	○	マージ	実装例
ヒープソート	${displaystyle nlog n}$	${displaystyle nlog n}$	$1$	×	選択
スムースソート	—	${displaystyle nlog n}$	$1$	×	選択
クイックソート	${displaystyle nlog n}$	$n^{2}$	$n$	×	パーティショニング	単純な実装ではメモリ使用量が $n$ になる。ピボット値として中央値を使えば、最悪時間が $O(nlog n)$
イントロソート	${displaystyle nlog n}$	${displaystyle nlog n}$	$log n$	×	混成
ペイシェンスソート	—	$n^{2}$	$n$	×	挿入	$O(nlog n)$ 以内にすべての最長増加部分列を探す。
ストランドソート	${displaystyle nlog n}$	$n^{2}$	$n$	○	選択
キクウテンチ/奇偶転置ソート	$n^{2}$	$n^{2}$	$1$	○	交換
シェアソート	${displaystyle n^{1.5}}$	${displaystyle n^{1.5}}$	$1$	×	交換

次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2^k を仮定している（<< は「十分小さい」）。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	n << 2^k?	備考
ハトノス/鳩の巣ソート	${displaystyle n+2^{k}}$	${displaystyle n+2^{k}}$	$2^{k}$	○	○
バケットソート	${displaystyle n+k}$	$n^{2}$	${displaystyle nk}$	○	×	入力データは定義域に一様分布すると仮定
フンフカソエ/分布数えソート	${displaystyle n+2^{k}}$	${displaystyle n+2^{k}}$	${displaystyle n+2^{k}}$	○	○
LSD 基数ソート	${displaystyle nk/s}$	${displaystyle nk/s}$	$n$	○	×
MSD 基数ソート	${displaystyle nk/s}$	${displaystyle n(k/s)2^{s}}$	${displaystyle (k/s)2^{s}}$	×	×
スプレッドソート	${displaystyle nk/log n}$	${displaystyle n(k-log n)^{0.5}}$	$n$	×	×	n << 2^k の場合の計算時間だが、それ以外の場合でもソート可能
キヤクシヤソウ/逆写像ソート	$n$ ?	N/A	$n$ ?	○	×

次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	大小比較	備考
ボゴソート	${displaystyle ncdot n!}$	∞	$1$	×	○	平均時間はクヌースのシャッフルを使った場合
ボゾソート	${displaystyle ncdot n!}$	∞	$1$	×	○	平均時間はボゴソートの約半分に漸近する。
ストゥージソート	${displaystyle n^{2.71}}$	${displaystyle n^{2.71}}$	$log n$	×	○
スリープソート	値の最大値×プロセス起動単位時間（実際には誤差あり）	同左	$n$ ?	×	?	条件が特殊。実用の正確性が保証されない。
ビードソート	N/A	N/A	—	N/A	×	専用ハードウェアが必要
タンシユンハンケエキ/単純パンケーキソート	$n$	$n$	$log n$	×	○	反転を定数時間で行えるものと仮定
ソーティングネットワーク	$log n$	$log n$	${displaystyle nlog n}$	○	×	大きさ $O(nlog n)$ の回路が必要。
バイトニックソート	${displaystyle log ^{2}n}$	${displaystyle log ^{2}n}$	${displaystyle nlog ^{2}n}$	×	×	計算時間とメモリ使用量はソーティングネットワークとして実装したときの値
バッチャー奇偶マージソート	${displaystyle log ^{2}n}$	${displaystyle log ^{2}n}$	${displaystyle nlog ^{2}n}$	×	×	計算時間とメモリ使用量はソーティングネットワークとして実装したときの値

比較ソートの理論限界

計算理論において、n個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でも O(n log n) 必要なことが知られている^[要出典]。O(n) で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意を要する。

最悪計算量が最低でもO(n log n) 必要である略証を示す。

ソーティングはデータの並べ替えである。
n個のデータの並べ替えは置換を用いて書け、置換はn!個ある。
スターリングの公式より、n!= O(nⁿ) 。

プログラム中の分岐はif文でしか起こらない。
1回のif文でプログラム中は2つに分岐するので、
n!個の置換をすべて実現する必要なif分岐の個数をmとすると、
2^m ≧ n!= O(nⁿ) でなければならない。
したがって、ソーティングの最悪計算量は最低でも m = O(n log n) である。

メモリ使用パターンとインデックスソート

ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。

例えば、再帰型のクイックソートは主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。

対策の一つとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある^[3]。

別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。

これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。

脚注・出典

^ パンチカードシステムの時代には、下位の桁から順に分類しては併合することがまさしく整列であった（O(n) のバケットソートになる）。

^ 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種類のソートアルゴリズムのアニメーションを一斉に実行でき、速度の違いを体感できる。

[1] パンチカードシステムの時代には、下位の桁から順に分類しては併合することがまさしく整列であった（O(n) のバケットソートになる）。

[2] Bubble Sort: An Archaeological Algorithmic Analysis Owen Astrachan

[3] tag sort Definition PCMAG.COM

搜尋此網誌