ソート

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

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

ソート (英: sort) は、データの集合を一定の規則に従って並べること^[1]。日本語では整列(せいれつ)、並べ替え(ならべかえ)、分類(ぶんるい)などと訳される^[1]。

主に配列や連結リストのような、リストデータ構造に分類されるコレクション(コンテナ)に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順(しょうじゅん、英: ascending order)を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順(こうじゅん、英: descending order)という。

対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。

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

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

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

表話編歴ソート
理論	計算複雑性理論ランダウの記号全順序リスト安定性ソーティングネットワーク比較ソート (英語版) 整数ソート (英語版)
交換ソート	バブルソートシェーカーソート奇偶転置ソートコムソートノームソートクイックソート
選択ソート	選択ソートヒープソートスムースソートデカルト木ソートトーナメントソート
挿入ソート	挿入ソートシェルソートツリーソート図書館ソートペイシェンスソート
マージソート	マージソート多層マージソートストランドソート
非比較ソート	基数ソートバケットソート計数ソートプロキシマップソート鳩の巣ソートバーストソートビーズソート
並行ソート	バイトニックソートバッチャー奇偶マージソートシェアソート
混成ソート	ティムソートイントロソート Jソートアンシャッフルソート (英語版)
その他	トポロジカルソートパンケーキソートスパゲティソート
非効率的/ ユーモラスソート	ボゴソートストゥージソートスリープソートエラーソート
カテゴリカテゴリ

概要

分類

安定ソート

内部ソートと外部ソート

比較ソート

計算量

手法

再帰

一覧

比較ソートアルゴリズムの最悪計算量の下界

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

脚注

出典

参考文献

関連項目

外部リンク

ソートアルゴリズムの視覚化