クイックソートは不安定(unstable)ですよという端的な例

が案外目につかないので残しておきましょう、と新人さんのトレーニング中に思い立ちました。検索して例に辿り着くのが手っ取り早いとはいえ、自分で例をひねり出してみるのも大切。ということでちょっと例を考えてみてから続きをどうぞ。 

今回は

  1. ピボットとして一つ選びそれをPとする。

  2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。

  3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。

  4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。

  5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

注:このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。

クイックソート – Wikipediaより引用(2016/8/1 時点)

この手順に従って例を挙げましょう。ピボットは対象範囲のデータ数がn(n≧2)のとき⌊n/2⌋番目のデータ(※1)とします。

まず極端な例から。データ数が2、値が両方とも2の場合です。何番目のデータかがわかるように上にインデックスを添えて図示したものが次の図です。

img000117

さらに、データが両方2では区別がつきにくいので便宜的に2A,2Bとします。

img000118

これを手順に従ってソートすると、2A,2Bが入れ替わってしまいます。最初のピボットは1番目のデータで(あたりまえですが)2です。左側から2以上を、右側から2以下を探し…

img000119

これが3の手順が完了した直後です。ここで手順4に従うと2Aと2Bはひっくり返ってしまいます。そこから手順2戻って、再び3の手順が完了した直後が下の図です。

img000121

iがjより左にないので手順5へ。

img000122

分割した領域が共にデータ数1なのでこれでソート完了です。というわけで、2A,2Bがひっくり返ってしまいました。

img000123



これだと、そもそもソートする必要がないしなんだか騙されたような気になりますね。もう一つ例を。

img000124

今度は多少それらしいデータです。重複した3つの”2”は先ほどと同様便宜的に2A,2B,2Cとしています。

初めは3番目のデータ=2がピボットとなります。手順3まで進めると…

img000126

この状態です。iがjより左にあるので2Aと2Cは入れ替えます。

img000127

手順2戻って、再び3の手順が完了した直後です。iとjが同じ、つまりiがjより左にないので手順5へ進むと、次のように領域が分割されます。

img000128

分割後はそれぞれの領域でソートするので、この時点の手順5により、元々2A, … , 2B, … , 2Cの順に存在していたデータのうち2Cが最終的に先頭になる、つまりソートが安定でないことが確定してしまいました。



ここまでも含め、2つ目の例全体を模式図にすると次のようになります。黄色がピボットとして採用したデータです。

img000130

 

どうでしょう、あらかじめ似た例が思い浮かんでいましたか?アルゴリズムの差異ごとの不安定性を示す例や、安定化するにはどうしたらいい?など、考えてみて下さい。



※1 ⌊x⌋は実数x以下の最大の整数。例では差しさわりありませんが、このピボットの選び方では引用元で触れられている無限ループが容易に発生します。max(⌊n/2⌋, 2)番目なら大丈夫。この場合、後半の例は{3,1,2,5,2,4}でも成り立ちます。

コメントを残す

メールアドレスが公開されることはありません。