ソートアルゴリズムの一覧
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/10 08:33 UTC 版)
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。 以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。 名称平均計算時間最悪計算時間メモリ使用量安定性手法備考バブルソート 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} ○ 挿入 最良計算時間が Θ ( n ) {\displaystyle \Theta (n)} になる。 シェルソート n log n {\displaystyle n\log n} ≧ n 1.5 {\displaystyle n^{1.5}} 1 {\displaystyle 1} × 挿入 最悪 Ω ( n 3 2 ) {\displaystyle \Omega (n^{\frac {3}{2}})} や Ω ( n 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} × パーティショニング メモリはコールスタック（素朴な実装では Ω ( 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} × 交換 次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2k を仮定している（<< は「十分小さい」）。 名称平均計算時間最悪計算時間メモリ使用量安定性n << 2k?備考ハトノス/鳩の巣ソート 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}} n k {\displaystyle nk} ○ × 入力データは定義域に一様分布すると仮定 フンフカソエ/分布数えソート n + 2 k {\displaystyle n+2^{k}} n + 2 k {\displaystyle n+2^{k}} n + 2 k {\displaystyle n+2^{k}} ○ ○ LSD 基数ソート n k / s {\displaystyle nk/s} n k / s {\displaystyle nk/s} n {\displaystyle n} ○ × MSD 基数ソート n k / s {\displaystyle nk/s} n ( k / s ) 2 s {\displaystyle n(k/s)2^{s}} ( k / s ) 2 s {\displaystyle (k/s)2^{s}} × × スプレッドソート n k / log n {\displaystyle nk/\log n} n ( k − log n ) 0.5 {\displaystyle n(k-\log n)^{0.5}} n {\displaystyle n} × × n << 2k の場合の計算時間だが、それ以外の場合でもソート可能 キヤクシヤソウ/逆写像ソート n {\displaystyle n} ? N/A n {\displaystyle n} ? ○ × 次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。 名称平均計算時間最悪計算時間メモリ使用量安定性大小比較備考ボゴソート n ⋅ n ! {\displaystyle n\cdot n!} ∞ 1 {\displaystyle 1} × ○ 平均時間はクヌースのシャッフルを使った場合 ボゾソート n ⋅ 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} × × 計算時間とメモリ使用量はソーティングネットワークとして実装したときの値
※この「ソートアルゴリズムの一覧」の解説は、「ソート」の解説の一部です。
「ソートアルゴリズムの一覧」を含む「ソート」の記事については、「ソート」の概要を参照ください。
- ソートアルゴリズムの一覧のページへのリンク
