🗺️ アルゴリズムクエスト
STAGE 5 ― クイックソート ―
クリア 0 / 9
🧭 地図
STAGE 5

クイックソート

分けて任せる。平均と最悪
🎯 ミッション
クイックソートの分け方と、平均 O(N log N)・最悪 O(N²) になる理由を説明できるようになろう。ばらばらの12個と並んでいる12個の両方で動かし、確認クイズに全問正解すれば合格。
未達成
ねこ博士
バブルソートは、隣どうしの比較の結果を、その2つの並びにしか使っていなかった。今日は、1つの基準(ピボット)を決めて、全員をその基準と比べる。基準より軽いものは左、重いものは右に分ける。
うさ美
分け終わったら、基準はちょうど左のグループと右のグループのあいだに置けばいい。左には基準より軽いものしかなく、右には重いものしかないので、基準の位置はもう動かない。確定です。
ねこ博士
そう。そして、左のグループと右のグループは、それぞれ同じやり方で並べればいい。左のグループの中でまた基準を決めて分け、右も分け……と、グループが1個になるまで続ける。これがクイックソートだ。1960年にトニー・ホーアが考えた。
うさ美
自分と同じやり方を、小さくなった問題にまた使うんですね。
ねこ博士
自分自身を使って小さな問題を解くことを再帰と呼ぶ。STAGE8 でまた詳しく見るよ。基準の選び方はいろいろあるけれど、ここでは一番簡単な「範囲の右端のものを基準にする」やり方を使う。
ねこ博士
比べる回数を考えよう。うまく基準が真ん中あたりの値になって、毎回ほぼ半分ずつに分かれたとする。1段目は N 個全部を基準と比べる。2段目は、半分ずつの2グループで、合わせて約 N 回。3段目も4グループで約 N 回。段は何段あるかな。
うさ美
毎回半分になるので、1個になるまでの段の数は、N を2で何回割ると1になるか。log₂ N 段です。1段あたり約 N 回だから、全部で約 N × log₂ N 回。
うまく半分ずつ分かれるとき:1段あたり約 N 回 × 段の数 log₂ N = 約 N log₂ N 回 → O(N log N) N = 100万:バブルソート約5000億回 / クイックソート約2000万回(約2万5千倍の差)
うさ美
でも、毎回半分に分かれるとは限らないですよね。基準がたまたま一番大きい値だったら?
ねこ博士
そこが大事なところだね。右端を基準にするやり方で、もう並んでいる荷物を並べようとすると、どうなるかな。
うさ美
右端は一番重いから、ほかの全員が左に行って、右のグループは空っぽ。1回で1つしか確定しない。次も残りの右端が一番重い……。毎回1つずつしか減らないので、比べる回数は (N−1)+(N−2)+…+1 で、バブルソートと同じ N(N−1)/2 回になってしまいます。
ねこ博士
そう。これが最悪の場合で、O(N²) だ。しかも「もう並んでいる」は、現実によくある入力なんだ。だから実際には、基準をランダムに選ぶ、3つ選んで真ん中の値を使う、などの工夫で、最悪の場合にめったに当たらないようにする。
クイックソート:平均 O(N log N)、最悪 O(N²)(基準が毎回端の値になるとき) 対策:基準をランダムに選ぶ/3つの真ん中を選ぶ/深くなりすぎたら別の並べ方に切り替える
うさ美
最悪の場合でも O(N log N) が約束される並べ方はないんですか?
ねこ博士
ある。たとえばマージソートは、先に半分ずつに分けておいて、並べ終わった2つの列を「先頭どうしを比べて小さいほうを取る」ことでつなぎ合わせる。いつでも O(N log N) だ。実は、比べることだけで並べる方法なら、どんな工夫をしても最悪 O(N log N) より速くはできないことが証明されている。クイックソートは平均がとても速く、マージソートは最悪でも速い。目的に応じて使い分けるんだ。

確認クイズ

Q1. クイックソートで、基準(ピボット)と比べて分け終わったあと、基準の位置について正しいのは?

Q2. 毎回ほぼ半分ずつに分かれるとき、クイックソートの比べる回数がおよそ N log₂ N になる理由は?

Q3. 右端を基準にするクイックソートで、もう並んでいる入力が最悪になる理由は?