tomoemonの日記スマートフォン用の表示で見るtomoemonの日記この広告は、90日以上更新していないブログに表示しています。2009-12-01不安定なマージソートアルゴリズムPHPのソート関数は不安定です。なんで安定ソートの一つや二つ初めから用意してくれないんだよ!と言いたいところですがPHPなので諦めます。ちなみにPythonは2.3から安定ソートであることが保証されています*1。安定なソートであれば問題無いのに、そうでないと困るのは次のような場合です。この$aをidでソートすると下のようになります。name=Aこれをさらにnameでソートしたときの結果が安定/不安定によって変化します。安定なソートであれば必ず次のようになりますが、不安定なソート関数であればid=2,id=3の順序が逆になる場合があります。name=Cこのように、複数のキーの組み合わせでソートしたいときに不安定なソートでは困るので、自前で安定なソートを実装する必要がありますが、それではどのアルゴリズムを使いましょうかという話になります。僕の場合は自前で安定なソートを実装するときは基本的にデータ数の少ない場合が多いので、バグを出さずにできるだけ手っ取り早く動かすことを考えてバブルソートを使うことが多いです。挿入ソートでも良いです。今回は少しデータ数が多くなるかもしれないという場面だったのでマージソートにしたのですが、久しぶりに書いてみたらあまり美しくないコードになったので、参考になるコードをと思ってググってみたわけですよ。C言語講座:マージソート以下のコードですね。非常にすっきりしたコードになっていると思いました。真ん中あたりの「逆順コピー」でtemp領域に入れることで、最後のマージがシンプルな条件判定で実現できています。temp[j--];}ところが!動かしてみるとなんかおかしいです。条件分岐とか不等号を書き間違えたのかと調べてみましたが問題ありません。一度元のソースを見てみると・・・・・・そもそもこのマージソートは安定になっていないじゃありませんか!落とし穴は最後のfor文でマージする部分です。実際のデータで説明します。ソートしたいデータを次のようにします。2分かりづらいので2は最初に並んでいた順に2A,2B,2Cとします。2Cこれを真ん中で分割してそれぞれをソートし、最後のマージをかけるぞという場面です。上のコードで言えば、2つのMergeSort呼び出しが終わった直後です。2Ctemp領域へのデータコピーが終わった時点でtempの状態は次のようになります。左半分は元の順番で格納して、右半分は逆順に格納します。2B]これを最後のループで取り出していくとどうなるでしょう。2Bを取り出すあらあら。2Bになってしまいました。j)はそれぞれの領域だけで使うものですが、この実装ではiが右半分に突入したりその逆がありえます。そのおかげでシンプルな実装にできているわけですが、それがあだとなって不安定なソートになってしまっています。安定にするのであれば下のように、左半分からチェックしていたiが中央をまたいだら中断して、残りの右半分は必ず右から一つずつ取り出すようにするぐらいしか思いつきません。美しくなくなってしまいました。temp[j--];}まとめこれまで、あるソートが安定か不安定かっていうのは単純にその字面だけ見てそういうもんなんだなと思い込んできましたが、実際のところその境目ってのはわりと単純なんですよね。安定なソート:隣同士を左(あるいは右から)順々に比較する不安定なソート:隣同士の比較をしない、比較の順序が変わるもっとかっちりした言い方があると思いますが、ざっくり言えばこんな感じなんだと思います。安定なソートの代表例であるバブルソート、挿入ソート、マージソートは隣同士の比較を行いますが、クイックソートはピボットの左右で離れた値を交換します。挿入ソートの改良版であるシェルソートやバブルソートの改良版であるコムソートは、隣同士ではなく間隔を広げて交換していくため不安定ソートになっています。temp[j]の比較が元の配列における値の比較と逆向きになってしまったために不安定なソートになってしまいました。間違えるだけで、不安定なソートに早変わりしてしまうこともあるのでソートを自前で実装するときはいろいろと注意しましょう。追記あーちょっと違うな。隣同士でなくてもいいのはマージソートで明らかなんだからその条件はいらない。比較・交換するときに常に元の配列における位置関係(元の順番で左にあったものと右に合ったものを比較する、あるいはその逆)を守るっていう条件だけで良さそう。離れた位置にあるものを交換すると、途中で比較の順序が逆になることがあるから不安定になる。比較ようこそGalaxyS3はてなブログをはじめよう!tomoemonさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。