安定ソートと不安定ソートアルゴリズム

ソートの安定性の意味とその重要性を学びます。安定アルゴリズム(マージソート、挿入ソート)と不安定アルゴリズム(クイックソート、ヒープソート)を比較します。

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

安定性が重要な理由

  1. 複数キーソート: 姓でソートし、次に部門で安定ソート。結果は部門順で、各部門内で名前順になります。
  2. データベース操作: SQL ORDER BY department, name は一貫した結果を生成するために安定ソートに依存します。
  3. ユーザーインターフェース: テーブルの列ヘッダーをクリックしてソートする際、等しい値に対して以前にソートされた列の順序が維持されるべきです。
  4. 再現性: 安定ソートは決定論的な出力を生成し、テストとデバッグに重要です。

不安定アルゴリズムを安定にできるか?

はい、元のインデックスを二次キーとして追加することで可能です。ただし、空間使用量がO(n)増加し、比較にオーバーヘッドが加わります。

JavaとPythonの選択

Java(オブジェクトのArrays.sort)とPython(list.sort)はどちらも安定なO(n log n)アルゴリズムであるTimsortを使用しています。安定性はオブジェクトをソートする際にほぼ常に望ましいためです。

ユースケース

安定性は、データベースエンジン、スプレッドシートアプリケーション、UIテーブルコンポーネントなど、複数のフィールドを持つレコードをソートするあらゆるアプリケーションに不可欠です。マルチレベルソート(1つのフィールドでソートし、次に別のフィールドでソート)を構築する際、安定性により複合比較関数の必要性がなくなります。

試してみる — Sorting Visualizer

フルツールを開く