不安定なマージソート
PHPのソート関数は不安定です。なんで安定ソートの一つや二つ初めから用意してくれないんだよ！と言いたいところですがPHPなので諦めます。ちなみにPythonは2.3から安定ソートであることが保証されています*1。
さて、安定なソートであれば問題無いのに、そうでないと困るのは次のような場合です。
$a = array(
array("id"=>2, "name"=>"A"),
array("id"=>1, "name"=>"C"),
array("id"=>3, "name"=>"A")
);
まず、この$aをidでソートすると下のようになります。
id=1, name=C id=2, name=A id=3, name=A
これをさらにnameでソートしたときの結果が安定／不安定によって変化します。安定なソートであれば必ず次のようになりますが、不安定なソート関数であればid=2,id=3の順序が逆になる場合があります。
id=2, name=A id=3, name=A id=1, name=C
このように、複数のキーの組み合わせでソートしたいときに不安定なソートでは困るので、自前で安定なソートを実装する必要がありますが、それではどのアルゴリズムを使いましょうかという話になります。
僕の場合は自前で安定なソートを実装するときは基本的にデータ数の少ない場合が多いので、バグを出さずにできるだけ手っ取り早く動かすことを考えてバブルソートを使うことが多いです。挿入ソートでも良いです。
ただ、今回は少しデータ数が多くなるかもしれないという場面だったのでマージソートにしたのですが、久しぶりに書いてみたらあまり美しくないコードになったので、参考になるコードをと思ってググってみたわけですよ。
Ｃ言語講座：マージソート
以下のコードですね。非常にすっきりしたコードになっていると思いました。真ん中あたりの「逆順コピー」でtemp領域に入れることで、最後のマージがシンプルな条件判定で実現できています。
#define MAX_DATA 10 int temp[MAX_DATA]; /* 最小でも配列と同じサイズの領域が必要 */ /* 配列 x[ ] の left から right の要素のマージソートを行う */ void MergeSort(int x[ ], int left, int right) { int mid, i, j, k; if (left >= right) return; /* ここでは分割しているだけ */ mid = (left + right) / 2; /* 中央の値より */ MergeSort(x, left, mid); /* 左を再帰呼び出し */ MergeSort(x, mid + 1, right); /* 右を再帰呼び出し */ /* x[left] から x[mid] を作業領域にコピー */ for (i = left; i <= mid; i++) temp[i] = x[i]; /* x[mid + 1] から x[right] は逆順にコピー */ for (i = mid + 1, j = right; i <= right; i++, j--) temp[i] = x[j]; i = left; /* i とj は作業領域のデーターを */ j = right; /* k は配列の要素を指している */ for (k = left; k <= right; k++) /* 小さい方から配列に戻す */ if (temp[i] <= temp[j]) /* ここでソートされる */ x[k] = temp[i++]; else x[k] = temp[j--]; }
ところが！
動かしてみるとなんかおかしいです。条件分岐とか不等号を書き間違えたのかと調べてみましたが問題ありません。もう一度元のソースを見てみると･･････そもそもこのマージソートは安定になっていないじゃありませんか！
落とし穴は最後のfor文でマージする部分です。
実際のデータで説明します。ソートしたいデータを次のようにします。
2, 1, 2, 2
分かりづらいので2は最初に並んでいた順に2A,2B,2Cとします。
2A, 1, 2B, 2C
これを真ん中で分割してそれぞれをソートし、最後のマージをかけるぞという場面です。上のコードで言えば、2つのMergeSort呼び出しが終わった直後です。
1, 2A, 2B, 2C
temp領域へのデータコピーが終わった時点でtempの状態は次のようになります。左半分は元の順番で格納して、右半分は逆順に格納します。
temp = [1, 2A, 2C, 2B]
これを最後のループで取り出していくとどうなるでしょう。
1. 1 <= 2B (i=0, j=3) の比較→1を取り出す、i++ 2. 2A <= 2B (i=1, j=3) の比較→2Aを取り出す、i++ 3. 2C <= 2B (i=2, j=3) の比較→2Cを取り出す、i++ 4. 2Bを取り出す
あらあら。1, 2A, 2C, 2Bになってしまいました。
通常マージソートでマージするときは左半分と右半分を順々に取り出していき、そのインデックス（i, j）はそれぞれの領域だけで使うものですが、この実装ではiが右半分に突入したりその逆がありえます。そのおかげでシンプルな実装にできているわけですが、それがあだとなって不安定なソートになってしまっています。
無理矢理安定にするのであれば下のように、左半分からチェックしていたiが中央をまたいだら中断して、残りの右半分は必ず右から一つずつ取り出すようにするぐらいしか思いつきません。あんまり美しくなくなってしまいました。
for(k = left; k <= right; k++){ if (temp[i] <= temp[j]) x[k] = temp[i++]; else x[k] = temp[j--]; if(i > mid) break; // 左端から見ていったiが中央をまたいだら中断 } // 右端から順番に取っていく for(; k <= right; k++){ x[k] = temp[j--]; }
まとめ
これまで、あるソートが安定か不安定かっていうのは単純にその字面だけ見てそういうもんなんだなと思い込んできましたが、実際のところその境目ってのはわりと単純なんですよね。
- 安定なソート：隣同士を左（あるいは右から）順々に比較する
- 不安定なソート：隣同士の比較をしない、比較の順序が変わる
もっとかっちりした言い方があると思いますが、ざっくり言えばこんな感じなんだと思います。安定なソートの代表例であるバブルソート、挿入ソート、マージソートは隣同士の比較を行いますが、クイックソートはピボットの左右で離れた値を交換します。また、挿入ソートの改良版であるシェルソートやバブルソートの改良版であるコムソートは、隣同士ではなく間隔を広げて交換していくため不安定ソートになっています。
今回のマージソートの実装では右半分が逆順になっていたことで、iが中央をまたいだ瞬間にtemp[i] <= temp[j]の比較が元の配列における値の比較と逆向きになってしまったために不安定なソートになってしまいました。（左の値 <= 右の値の比較が、右の値 <= 左の値になってしまった）
ちなみに、安定なソートアルゴリズムであっても実装の際に不等号の < と <= を間違えるだけで、不安定なソートに早変わりしてしまうこともあるのでソートを自前で実装するときはいろいろと注意しましょう。
追記
あーちょっと違うな。隣同士でなくてもいいのはマージソートで明らかなんだからその条件はいらない。比較・交換するときに常に元の配列における位置関係（元の順番で左にあったものと右に合ったものを比較する、あるいはその逆）を守るっていう条件だけで良さそう。離れた位置にあるものを交換すると、途中で比較の順序が逆になることがあるから不安定になる。
