比較・疑問解決 · 基礎から応用へ

安定ソートと不安定ソート

同じキーを持つレコードの順序を追い、安定性、複数キーの整列、再現性、実装の費用を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 等しいキーの元の順序を保つか
  2. 点数が同じ二人を追う
  3. 複数回の整列では下位キーから行う
  4. アルゴリズム名より実装の契約を読む
  5. 再現性が必要なら同順位の意味を決める
  6. この記事をロゲイアに質問する理解を確かめる

等しいキーの元の順序を保つか

安定ソートは、比較キーが等しい要素同士について、入力にあった相対順序を出力でも保ちます。安定という語は、実行時間が一定、落ちない、どんな入力でも高速という意味ではありません。非安定ソートは、等しいキーの順序を保つ保証がない方式です。必ず毎回逆転させるという意味でもなく、一つの入力例で順序が保たれたから安定な実装と証明できるわけでもありません。何を等しいと判定するかは、キー関数と比較の契約で決まります。レコード全体の内容が違っていても、キーが同じならこの保証の対象になります。

観点安定ソート非安定ソート
同キーの相対順序入力順を保つ保持を保証しない
一つの例で順序を保持契約と一致起こり得るが保証の証明ではない
一意な業務順序入力順や追加キーの定義も必要追加キーを明示して定義する

点数が同じ二人を追う

入力を(A,80)、(B,70)、(C,80)とし、点数の昇順で並べるとします。安定ならBの後にA、Cの順で80点の二人が続きます。非安定ならB、C、Aという結果も許され得ますが、B、A、Cになる実行もあり得ます。点数だけを見れば、どちらも正しく昇順です。つまり、キーが整列している条件と、同キーの順序を保つ条件は別です。元の順序が受付順などの意味を持つなら安定性が役立ちます。一方、元の順序が並行処理などで決まっていない場合、安定なソートだけでは業務上の一意の順序は定まりません。

Python
records = [('A', 80), ('B', 70), ('C', 80)]
result = sorted(records, key=lambda item: item[1])
assert [name for name, score in result] == ['B', 'A', 'C']

複数回の整列では下位キーから行う

担当者を第一キー、日付を第二キーにしたい場合、まず日付で並べ、その後に担当者で安定ソートすると、同じ担当者の中では先の日付順が残ります。この順番を逆にすると、最後の日付ソートが第一キーになってしまう場合があります。複数のキーを組にして一回で比較する方法もあります。どちらを使う場合も、昇順・降順、欠損値、大文字小文字などの扱いを定めます。「安定ならどんな順番で何回ソートしても同じ」ではありません。後から適用するキーが優先され、同順位のときだけ前の順序が残るという規則を、実際のレコードで確かめてください。

アルゴリズム名より実装の契約を読む

標準的な安定マージでは、同じキーのとき左の列から先に取り出すことで相対順序を保てます。典型的な配列内クイックソートは安定性を保証しませんが、安定な変種を作ることは可能です。したがって名前だけで断定せず、使うライブラリの契約を確認します。Pythonのsortとsortedは安定性を保証する例です。一方、安定性があっても補助領域や比較回数の上限は別の性質であり、それらも必要なら確認します。対象のキーが一貫した比較規則を満たさない場合は、ソート自体の前提が崩れることもあるので、比較関数の実装も検査してください。

再現性が必要なら同順位の意味を決める

監査用の出力やページ分割などで順序を再現したいなら、同じ主キーの中で何を優先するかを明示する方が確実です。時刻だけでは同値が生まれるので、識別子など一意に近い追加キーを使う設計が候補になります。SQLでもORDER BYが一部の列しか指定しない場合、同順位を必ず希望の順に返すとは限りません。安定な関数を選ぶことと、入力や業務上の順序を定めることは別です。テストでは同キーの識別子の順序と、全体のキー順序を別に確認し、結果の一致だけでなく、必要な契約を満たしているかを検証します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ