１１．クイックソート

１１．１．クイックソートとは

クイックソートはマージソートに良く似たソーティングアルゴリズムです。マージソートと同じく、データを分割してそれぞれをソーティングし、最後に1つにあわせます。それぞれのソーティングにクイックソートを利用する再帰的な点も、マージソートに似ています。

マージソートと異なるのは、データの分割の方法です。マージソートは「個数が均等になるように」2つに分割するのに対し、クイックソートは「基準値との比較」で2つに分割します。この基準値の取り方次第によっては、1つと残りの全部というような、極端な別れ方になることもありえます。

１１．２．データの分割

クイックソートが優れている点は、分割したデータを1つにあわせるところにあります。マージソートではそれぞれ比較作業をする必要がありますが、クイックソートではその必要がありません。基準値の大小で2つに別れているためです。

しかし前節の通り、この基準値次第によっては「1つと残りの全部」というような極端な分割のされ方をします。クイックソートもマージソートと同じく再帰的に分割を繰り返していくので、極端な分割が続くと下図のように非常に効率の悪いものになってしまいます。

クイックソートもマージソートと同じく、なるべく均等に分割される方が高速に実行できます。その場合の計算量はO(nlogn)で、マージソートと同じです。しかし上記のように、極端な分割になった場合の計算量はO(n²)と悪くなり、マージソートに負けてしまいます。しかしだいたいの場合において、クイックソートは最も高速に実行できるソーティングアルゴリズムと言われています。

１１．３．基準値

クイックソートは基準値のとり方で実行性能が変わってきます。しかし基準値の計算に時間がかかってしまっては、全体としてソーティングに時間がかかることになりますので意味がありません。基準値のとり方としては、以下のようなものが考えられます。

• 先頭の値
• 先頭と末尾の値の平均
• 「先頭の値」「末尾の値」「配列の真中の値」のメディアン（並べた時に真ん中に来る値）

実際には、最も単純に「先頭の値」を選択しても、前節のような極端な分割が続くことはほとんどありません。

（実習課題）

以下のプログラムを作成しなさい。

• 乱数発生プログラムで生成した数字を読み込み、それに対してクイックソートを実行する。
• 基準値は「11.3節」の3つの方法のいずれかを、実行時にオプションで指定できるようにすること。
• ソーティングの開始から終了までかかった時間を表示すること。ただし数字を読み込む時間・表示する時間は含まない。
• qsort関数を使用してはならない。
• （ヒント）時間の計測にはtime関数を使用する。

1　2

（実習課題）

「選択ソート」「バブルソート」「ヒープソート」「マージソート」「クイックソート」の5つの実行速度を比較しなさい。

• 全てのソーティングプログラムを、ソーティングの開始から終了までかかった時間を表示できるように作り変える。
• 乱数発生プログラムで生成した同じ数字を読み込んだ際に、それぞれかかった時間を比較する。
• 発生させる数字の数を「100」「200」「300」「500」「1000」と増やしていった場合の実行時間の変化を比較する。