7種類が同じ入力を同時に整列します。1回の更新で比較や移動を1ステップ進めるため、早く終わるほど集計したステップ数が少ないことを示します。実際のCPU実行時間の比較ではありません。入力によって順位は変わります。
同じ配列で7種類の整列アルゴリズムを比較するシミュレーター
入力
ほぼ整列済みなら挿入ソートとバブルソートが有利ですが、逆順では処理が増えます。マージソートとヒープソートは入力順序の影響が小さめです。表のアルゴリズム名から詳細な実験へ進めます。
計算量の一覧
| アルゴリズム | 最良 | 平均 | 最悪 | 追加領域 | 安定性 |
|---|---|---|---|---|---|
| バブル | O(n) | O(n²) | O(n²) | O(1) | はい |
| 選択 | O(n²) | O(n²) | O(n²) | O(1) | いいえ |
| 挿入 | O(n) | O(n²) | O(n²) | O(1) | はい |
| クイック | O(n log n) | O(n log n) | O(n²) | O(log n) | いいえ |
| マージ | O(n log n) | O(n log n) | O(n log n) | O(n) | はい |
| ヒープ | O(n log n) | O(n log n) | O(n log n) | O(1) | いいえ |
| 計数 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | はい |
kは計数ソートの値域です。安定ソートは同じ値の元の順序を保ちます。名前で整列した後に点数で整列するなど、複数の基準を順に適用するときに役立ちます。
どのアルゴリズムを使うか
通常は言語の組み込みソート
Pythonのsort()は安定で、最悪時間計算量はO(n log n)です。一般的な整列には、十分に検証された組み込み実装を使いましょう。
最悪でもO(n log n)が必要な場合
安定性が必要で追加メモリを使えるならマージソート、配列の追加領域を一定に抑えたいならヒープソートが候補です。
ほぼ整列済み・小さな入力
挿入ソートが得意な条件です。多くの汎用ソートでも小区間の処理に使われます。
狭い値域に大量の整数
計数ソートは値同士を比較せずO(n + k)で処理します。頻度だけが必要なら保存領域も減らせます。
演習：ソートキーを選ぶ
多くの問題ではソートの自作よりキーの選択が重要です。タプルのキーは順に比較され、数値に負号を付けるとその項目を降順にできます。
a.sort() # 安定・リストを直接更新
b = sorted(a, reverse=True) # 降順の新しいリスト
people.sort(key=lambda p: (-p[1], p[0])) # 点数は降順、名前は昇順おおまかな目安では、二乗時間のアルゴリズムは数千要素なら使える場合がありますが、10万要素ほどでは高コストです。限界は言語・機器・処理内容に依存するため、固定の時間目安ではなく計測で判断してください。