ALDS1_2_C:

安定なソート

アルゴリズムを設計・選択するときの重要なポイントの１つがその計算量ですが、ソートのアルゴリズムに関しては、それが「安定なソート」であるかを考慮に入れる必要があります。キーが同じである要素が2つ以上存在するデータをソートした場合、ソート前とソート後でそれらの要素の順番が変わらないようなソートを安定なソート（stable sort）といいます。

次の例は、'3A'と'3B'の２つの 3 をこの順で含む配列に対して、選択ソートを行った不安定なソートの実例です。

ソートが終わると'3B'と'3A'となり順番が逆になってしまうことが分かります。

バブルソートは、配列要素の隣同士のみを比較・交換するので、要素のキーが同じだった場合、それらの順番が入れ替わることはありません。従ってバブルソートは安定なソートです。ただし隣同士を比較する演算 data[j] < data[j-1] に等号を入れて data[j] <= data[j-1] としてしまうと安定ではなくなるので注意が必要です。

挿入ソートは離れた要素を直接交換することはありません。挿入の位置を選ぶ過程の要素の動きは、バブルソートの原理に類似しています。よって、挿入ソートは安定なソートアルゴリズムです。

この問題については、ソートの結果が安定かどうかを調べるには、$N$の値が小さいので、次のようなカードの組に対する順番を愚直に調べる $O(N^4)$ のアルゴリズムを適用することができます。

1 isStable(in, out)
2   for i = 0 to N-1
3     for j = i+1 to N-1
4       for a = 0 to N-1
5         for b = a+1 to N-1
6           if in[i] と in[j] の数字が等しい && in[i] == out[b] && in[j] == out[a]
7             return false
8 return true

この問題では $O(N^4)$ のアルゴリズムで十分ですが、より $N$ が大きい場合は工夫が必要です。バブルソートは安定なソートなので、常に「Stable」を出力します。選択ソートは安定なソートではないので、出力結果を調べる必要がありますが、バブルソートの結果と比較することによって $O(N)$で判定を行うことができます。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。