が案外目につかないので残しておきましょう、と新人さんのトレーニング中に思い立ちました。検索して例に辿り着くのが手っ取り早いとはいえ、自分で例をひねり出してみるのも大切。ということでちょっと例を考えてみてから続きをどうぞ。
今回は
-
ピボットとして一つ選びそれをPとする。
-
左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
-
右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
-
iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
-
2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。
注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。
クイックソート – Wikipediaより引用(2016/8/1 時点)
この手順に従って例を挙げましょう。ピボットは対象範囲のデータ数がn(n≧2)のとき⌊n/2⌋番目のデータ(※1)とします。
まず極端な例から。データ数が2、値が両方とも2の場合です。何番目のデータかがわかるように上にインデックスを添えて図示したものが次の図です。
さらに、データが両方2では区別がつきにくいので便宜的に2A,2Bとします。
これを手順に従ってソートすると、2A,2Bが入れ替わってしまいます。最初のピボットは1番目のデータで(あたりまえですが)2です。左側から2以上を、右側から2以下を探し…
これが3の手順が完了した直後です。ここで手順4に従うと2Aと2Bはひっくり返ってしまいます。そこから手順2戻って、再び3の手順が完了した直後が下の図です。
iがjより左にないので手順5へ。
分割した領域が共にデータ数1なのでこれでソート完了です。というわけで、2A,2Bがひっくり返ってしまいました。
…
これだと、そもそもソートする必要がないしなんだか騙されたような気になりますね。もう一つ例を。
今度は多少それらしいデータです。重複した3つの”2”は先ほどと同様便宜的に2A,2B,2Cとしています。
初めは3番目のデータ=2がピボットとなります。手順3まで進めると…
この状態です。iがjより左にあるので2Aと2Cは入れ替えます。
手順2戻って、再び3の手順が完了した直後です。iとjが同じ、つまりiがjより左にないので手順5へ進むと、次のように領域が分割されます。
分割後はそれぞれの領域でソートするので、この時点の手順5により、元々2A, … , 2B, … , 2Cの順に存在していたデータのうち2Cが最終的に先頭になる、つまりソートが安定でないことが確定してしまいました。
…
ここまでも含め、2つ目の例全体を模式図にすると次のようになります。黄色がピボットとして採用したデータです。
どうでしょう、あらかじめ似た例が思い浮かんでいましたか？アルゴリズムの差異ごとの不安定性を示す例や、安定化するにはどうしたらいい？など、考えてみて下さい。
—
※1 ⌊x⌋は実数x以下の最大の整数。例では差しさわりありませんが、このピボットの選び方では引用元で触れられている無限ループが容易に発生します。max(⌊n/2⌋, 2)番目なら大丈夫。この場合、後半の例は{3,1,2,5,2,4}でも成り立ちます。