安定ソートと不安定ソートアルゴリズム
ソートの安定性の意味とその重要性を学びます。安定アルゴリズム(マージソート、挿入ソート)と不安定アルゴリズム(クイックソート、ヒープソート)を比較します。
Algorithm Analysis
詳細な説明
ソートの安定性とは?
ソートアルゴリズムが安定であるとは、等しいキーを持つ要素の相対順序を保持することです。つまり、2つの要素が同じソートキーを持つ場合、出力では入力と同じ順序で表示されます。
視覚的な例
成績でソート(名前の順序は無視):
| 入力 | 名前 | 成績 |
|---|---|---|
| 1 | Alice | B |
| 2 | Bob | A |
| 3 | Carol | B |
| 4 | Dave | A |
安定ソート(成績順): Bob(A), Dave(A), Alice(B), Carol(B) — 各成績内で元の順序が保持。
不安定ソートでは: Dave(A), Bob(A), Carol(B), Alice(B) — 成績内の相対順序が変化する可能性。
どのアルゴリズムが安定か?
| 安定 | 不安定 |
|---|---|
| マージソート | クイックソート |
| 挿入ソート | ヒープソート |
| バブルソート | 選択ソート |
| カウンティングソート | シェルソート |
| 基数ソート | Introsort |
| Timsort |
安定性が重要な理由
- 複数キーソート: 姓でソートし、次に部門で安定ソート。結果は部門順で、各部門内で名前順になります。
- データベース操作: SQL
ORDER BY department, nameは一貫した結果を生成するために安定ソートに依存します。 - ユーザーインターフェース: テーブルの列ヘッダーをクリックしてソートする際、等しい値に対して以前にソートされた列の順序が維持されるべきです。
- 再現性: 安定ソートは決定論的な出力を生成し、テストとデバッグに重要です。
不安定アルゴリズムを安定にできるか?
はい、元のインデックスを二次キーとして追加することで可能です。ただし、空間使用量がO(n)増加し、比較にオーバーヘッドが加わります。
JavaとPythonの選択
Java(オブジェクトのArrays.sort)とPython(list.sort)はどちらも安定なO(n log n)アルゴリズムであるTimsortを使用しています。安定性はオブジェクトをソートする際にほぼ常に望ましいためです。
ユースケース
安定性は、データベースエンジン、スプレッドシートアプリケーション、UIテーブルコンポーネントなど、複数のフィールドを持つレコードをソートするあらゆるアプリケーションに不可欠です。マルチレベルソート(1つのフィールドでソートし、次に別のフィールドでソート)を構築する際、安定性により複合比較関数の必要性がなくなります。