クイックソートの考え方は？

クイックソートプログラム

　前ページの説明をプログラムにしてみたものが図2のquicksortです。一見わかりづらいかもしれませんが、前述の説明をそのまま表現したものです。少し説明しましょう。

　（1）は説明では「ある数値」と呼びましたが、ここでは $pivot としています。軸足のことですね。今は説明のとおりに、左端の数値をピボットにします。

　（2）、（3）が「視点」です。それぞれ、左端と右端から中央に向かって動いていきます。

　（4）、（5）が視点の移動です。ピボットよりも小さいものがある間は左側の視点は動かし（4）、ピボットよりも大きいものがある間は右の視点を動かします（5）。視点が止まるのは、左側ではピボットに等しいか大きいものが現れたときです。右側ではピボットに等しいか小さいものが現れたときです。

　（6）もし視点がぶつかるか交差すれば区間の分割と入れ替えは終わりなのでおしまいになります。

　（7）視点の移動が止まったところで（視点の交差がない場合）、それぞれの視点の位置にある数値を入れ替えます。ここでは前回も出てきたswap関数を使います。

　このqsort関数を使うためには少しおぜん立てが必要です。引数に配列と、ソートしたい区間のインデックスを渡す必要があるからです。テスト用のプログラムも併せて示します（図2のプログラム全体）。

クイックソート分析

　さて、前回示したものよりはずっと複雑怪奇なプログラムになりました。しかし、その名の示す通り、この方法はとても速いのです。バブルソートでは平均計算回数は n^2（nの2乗）に比例すると説明しましたが、このquicksortは平均でn*log（n）に比例することがわかっています。「平均で」と言ったのは、区間の分割のしかたがまずいときは、やはりnの2乗に比例します。

　「区間の分割のしかたがまずい」というのは、区間がきれいに半分に分かれれば良いのですが、ピボットの数値の選び方が悪ければ、左側は1個だけで、残りが全部右側というようになるかもしれないということです。そのような最悪の場合が続くと、1回の分割で1個の入れ替えしかできず、結局n回繰り返すことになります。

　区間の分割をできるだけ左右同じになるようにするためには、ピボットの数値として、配列に現れる数値の平均値（中央値）を取るのがベストということになります。が、この平均値を計算するための労力も無視できませんから、一般には、配列に現れる3個程度の数値の平均値を使うか、配列の真ん中に位置する数値を使うなどの便宜的な方法を採用します。

　今回の説明で使った方法は配列の左端の数値を使うというものでしたが、今回はまずまずの計算回数だったと言えるでしょう。