クイック・マージの考え方

分けてから片づける

前回までの3つの整列法は、どれも要素数が増えると比較回数がその2乗で増えました。100個で約5000回、1000個なら約50万回です。これを大きく減らすのが、クイックソートとマージソートに共通する分割統治という考え方です。難しい問題をそのまま解かず、同じ形の小さい問題に割って解き、結果を組み立て直します。前章の再帰がここで効いてきます。

なぜ速くなるのかを先に押さえます。n 個を2つに割り、その片方をまた2つに割る、と続けると、1個になるまでの割る回数はおよそ log2(n) 回です。各段では全体でおよそ n 個ぶんの作業をするので、全体の手間はおよそ n × log2(n) になります。n が 1000 なら 50万回が1万回ほどに減る計算です。

クイックソートは基準値で仕分ける

クイックソートは、まず基準値を1つ選びます。この基準値をピボットと呼びます。次に、ピボットより小さい値を左へ、大きい値を右へ寄せます。この時点でピボットの位置は確定します。あとは左のかたまりと右のかたまりに対して、同じことをもう一度やるだけです。

{5, 3, 4, 1, 2} でピボットを 3 とすると、まず {1, 2} と 3 と {5, 4} に分かれます。左の {1, 2} をさらに分けると並び終わり、右の {5, 4} も同じです。最後につなげると {1, 2, 3, 4, 5} になります。

特徴は、分けるときに仕事をして、つなぐときは何もしない点です。速度は平均で n log n ですが、ピボットの選び方が悪く毎回ほとんど分けられない場合は n の2乗まで悪化します。並び終わったデータに対して端の値をピボットに選ぶと、この最悪の形になります。

マージソートは並んだ2つを合流させる

マージソートは逆で、まず何も考えずに半分ずつに割り切ります。1個になったらそれ自体が並んでいるとみなし、そこから2つの並んだ列を合流させていきます。合流は、両方の先頭を比べて小さいほうを取り出す、を繰り返すだけです。

{5, 3, 4, 1, 2} なら {5, 3, 4} と {1, 2} に割り、それぞれを並べて {3, 4, 5} と {1, 2} にしてから合流します。先頭の 3 と 1 を比べて 1、次に 3 と 2 を比べて 2、というように取り出すと {1, 2, 3, 4, 5} が得られます。

特徴は、分けるときは何もせず、つなぐときに仕事をする点です。どんなデータでも必ず n log n で終わる安定した速さが強みで、代わりに合流用の作業領域を別に必要とします。この作業領域が要るか要らないかは、比較の問題でよく問われます。

試験での聞かれ方

擬似言語で全体を書かせる出題は多くありません。多いのは、ピボットで分けた直後の並びを選ばせる問題、合流の途中でどちらから何が取り出されるかを追う問題、そして「分割統治とはどれか」という用語の問題です。分けるときに仕事をするのがクイック、つなぐときに仕事をするのがマージ、という対比で覚えておくと迷いません。