整列７

クイックソートの特徴

●クイックソートは、バブルソートや選択ソートに比べて速いソートですが、他のソートとの比較よりも注目しなければならないことがあります。それは、データ数が多くなったときでもそれほど遅くならないということです。

実際に時間を計って

●実際に時間を計ってもわかりますが、バブルソートや選択ソートはデータ数が２倍になると４倍の時間がかかります。クイックソートでは２.１〜２.２倍ぐらいです。これはひとえに分割して比較することから来ています。

ちょっと理屈で考えて

●１００個のデータを並べ替えるのに４秒かかったとします。データが２倍の２００個になったなら、時間は４倍の１６秒です。２００個を２つに分けてそれぞれ整列させたら１００個の整列が２回ですから時間も２回分の８秒で済みます。２００個を大きいものと小さいものに２分できれば、１００個づつ整列してあとであわせることで２００個整列したことになります。大きいものと小さいものに分けるのに多少かかったとしても１０秒程度で整列できます。

●１０００個ならどうでしょうか。数が１０倍ですから時間は１００倍で４００秒です。これを１００個づつ１０グループに分けて並べれば時間は１０倍の４０秒です。分ける時間を入れても５０秒程度でできます。

プログラムをみて手数を数えると

●大きいものと小さいものに分ける時間は短いだろうと予測しましたが、そうでないかもしれません。そんなときにはプログラムをみて手数を数えるということが必要になります。バブルソートや選択ソートが Ｏ( n² ) であるというのは、プログラムから比較の回数や代入の回数をおおざっぱに数えて出した結果です。n 個のデータを並べ替える手間はｎの２乗ていどだというわけです。

●クイックソートの手数は Ｏ( ｎ log ｎ ) 程度と調べられています。ここでは log n は正確には log₂ｎ で、 ２^ｋ＝ｎであるような、ｋの値をいいます。

●比べてみましょう。ｎlogｎがクイックソート、ｎ²が選択・バブルソートです。ｎが４あたりまでは半分ですが、1000になると約9966は約10000と見なせるので、百分の１の手数で計算できることになります。これはｎが大きくなるほど差が広がります。

●グラフにしてみました

●ｎが大きくなるともっと差が広がります。

注意１

●「クイックソートは世の中で最も速いソートアルゴリズムとして知られています」と書きましたが、「クイックソートが最速」と暗記しないでください。もっと速いアルゴリズムが発見される（ている）かもしれません。手数が Ｏ( ｎ log ｎ ) 程度になるアルゴリズムは他にもあります。どのアルゴリズムが速いかというのはプログラム言語の種類にもよりますし、種類は同じでもシステムによって違うものなのです。

●ですから、普通ソートアルゴリズムの優劣を考えるときは実際の速さでなく、手数の概算で考えます。これがデータの初期値の並び方によっても変わる場合があり、なかなか難しいのです。ある条件では Ｏ( ｎ ^1.2 ) 程度になるアルゴリズムも知られています。これは、 Ｏ( ｎ log ｎ ) よりも優秀です。

注意２

●バブルソートや選択ソートはデータがｎの時、手数が Ｏ( n² ) で、データ数が２倍になったら、２²＝４倍になるというのはその通りです。でもｎに２を代入してそうなるのではありません。（２ｎ）²が、ｎ² の４倍であるということです。

●従って、クイックソートの手数は Ｏ( ｎ log ｎ ) 程度ですが、データ数が２倍になったら、 ｎ log ｎ ＝２ 1og₂２＝２倍とはなりません。(２ｎの時の手数)÷(ｎの時の手数)で計算します。つまり（２ｎ 1og₂２ｎ）÷（ｎ 1og₂ｎ）を計算することになります。