· 開発

安定ソート（stable sort）とは：同じ値の並び順が保たれるソート

安定ソートの意味、複数のキーで並べ替えるときに重要な理由、Python・JavaScript・Java・C++の標準ソートが何を保証しているかを仕様と公式ドキュメントをもとに整理しました。

開発アルゴリズム

表の「日付」列をクリックして並べ替えたら、同じ日付の行の順番が入れ替わってしまった。これはバグとは限りません。ソートが**安定（stable）**かどうかの違いです。

安定ソートの意味

比較したときに等しいとみなされる要素どうしが、並べ替えた後も元の相対的な順序を保つソートを安定ソートと呼びます。Python のドキュメントでは「同じキーを持つレコードが複数あるとき、元の順序が保たれる」と説明されています。

注文一覧を日付で並べ替える例で考えます。

元の順番 注文 日付
1 A 9月2日
2 B 9月1日
3 C 9月2日

日付順に並べると B が先頭に来ます。安定ソートなら、その後は必ず A、C の順です。安定でないソートでは C、A になることもあります。どちらも「日付順」という条件は満たしているので誤りではありませんが、同じ日付の中の順番は保証されません。

整数だけの配列のように、等しい値どうしを区別する手段がなければ安定性は意味を持ちません。差が出るのは、レコードやオブジェクトのようにソートのキー以外の情報も持っている場合です。

なぜ重要か：複数のキーで並べ替える

安定ソートがいちばん役立つのは、何回かに分けて並べ替えるときです。「部署ごとに、同じ部署の中では給与等級順に」並べたいなら、副キーで先にソートし、主キーで後からソートします。二回目のソートが安定なので、同じ部署の中には一回目の結果がそのまま残ります。

Python の公式ドキュメントでもこの方法が紹介されています。

from operator import attrgetter

s = sorted(students, key=attrgetter("age"))            # 副キー：年齢
s = sorted(s, key=attrgetter("grade"), reverse=True)   # 主キー：学年（降順）

表の UI で列見出しを順にクリックしたとき、先にクリックした列の順番が同順位の中に残るのも同じ仕組みです。ソートが安定でなければ、この動きは期待できません。

言語ごとの標準ソートが保証していること

「たいてい安定しているようだ」ではなく、仕様やドキュメントが保証しているかを確認します。実装がたまたま安定していても、仕様で保証されていなければバージョンや環境によって変わる可能性があります。

言語 関数 安定性
Python list.sort()、sorted() 保証あり。ドキュメントに「guaranteed to be stable」と明記
JavaScript Array.prototype.sort() ECMAScript 2019（第10版）から仕様で保証。ただし比較関数が一貫している場合に限る（後述）。それ以前の版では保証されていなかった
Java Arrays.sort(Object[])、List.sort() 保証あり。「equal elements will not be reordered」
Java Arrays.sort(int[]) などのプリミティブ型 安定性への言及なし。実装は Dual-Pivot Quicksort だが、同じ int 値どうしは区別できないので問題にならない
C++ std::sort 保証なし。規格は std::stable_sort にだけ安定（Stable）と記し、std::sort にはその条件がない
C++ std::stable_sort 保証あり。ただし追加メモリが足りないと比較回数が N·log²N 程度まで増える

Python のソートは Timsort で、Java の List.sort() の実装も Python の Timsort をもとにした安定なマージソートだとドキュメントに書かれています。

JavaScript：安定なのは比較関数が正しいときだけ

ECMAScript の仕様（ECMA-262）が Array.prototype.sort に安定性を求めるのは、比較関数が**一貫した比較関数（consistent comparator）**である場合だけです。そうでなければソート順は実装定義（implementation-defined）になり、安定性どころか結果が並べ替えられていることさえ保証されません。

比較関数 (a, b) => … は数値を返す必要があり、その符号で意味が決まります。

  • 負の数：a が b より前
  • 正の数：a が b より後
  • 0：両者は等しい（安定ソートなら元の順序を保つ）

よくある間違いは、比較の結果を真偽値で返すことです。

players.sort((a, b) => a.score > b.score);   // 正しくない比較関数
players.sort((a, b) => a.score - b.score);   // 正しい比較関数（昇順）

仕様は比較関数の戻り値を数値に変換するので、true は 1、false は 0 になります。a.score < b.score のときは負の数を返すべきところで 0 が返り「等しい」という意味になり、引数を入れ替えて呼ぶと 1 が返って「等しくない」になります。これは一貫した比較関数ではないので、あるエンジンでたまたま正しく並んだとしても、仕様上は結果を当てにできません。

比較関数を渡さない場合、既定のソートは値を文字列に変換して比較します（undefined は末尾に回ります）。そのため数値の配列も辞書順になります。

[10, 9, 1].sort();                 // [1, 10, 9]
[10, 9, 1].sort((a, b) => a - b);  // [1, 9, 10]

安定性に頼らない方法

安定でないソートを使う必要がある場合や、コードを読む人に安定性を意識させたくない場合は、比較に同順位を解消するキーを加える方法があります。たとえば日付が同じなら注文番号で比べるようにすれば、どのソートアルゴリズムを使っても結果が一つに決まります。

orders.sort((a, b) => a.date.localeCompare(b.date) || a.id - b.id);

C++ で std::sort にこのような完全な基準を与えれば、std::stable_sort を使わなくても決定的な結果が得られます。逆に「元の入力順」そのものが意味のある基準で、別に保存された値がない場合は、安定ソートを使うのがいちばん簡単です。

参照した仕様とドキュメント

ブログへ