クイックソート

　クイックソート（quick sort）は、一般的なデータに対しては最速でソートを行いますから、世界中で広く使われている高速ソート技法です。

特　徴

• 　一般的なデータに対しては、他のソート法に比べて圧倒的に速い。
• 　フォワードスキャンとリバーススキャンがとにかく速いうえ、必要なときしかスワップしないのが高速性の最大ポイント。
• 　世界中で研究された結果、苦手なデータの存在も広く普及したため、時々、故意に苦手なデータをソートさせるイジメにあっている。
• 　一部のサーバ管理者はこのいじめが原因でサーバーの能力が低下するのを懸念し、マージソートを積極的に採用しているらしい。この話がどこまで本当かは筆者にはわからない。
• 　再帰コール型ではなく、スタックを自前で用意した非再帰コール型にすると、スタックの使用量を大幅に少なくできる傾向がある。

　なお実際の使い方では、残りレコード数が少なくなったとき、セレクションソートかインサーションソートに切り替えて、処理が重いクイックソートから、処理が軽い物へ変更する場合が多いです。ただ、特に名もないこの切り替え手法が、イントロソートと勝手に勘違いされることが多いようです。

危険なソースリストに注意！

　一部のクイックソートの紹介記事では、配列の先頭をピボットにするリストを掲載していることがあります。ピボットの値は、データの範囲内であれば何でも構わないのが原則なので、先頭でも構わないという判断かと思います。

　ただし、その方法では、ゼロクリアしたデータのソートとか、すべて同一定数のソートを行ったとき、最悪計算量、または最悪計算量に近い状態になりがちです。この現象をきちんと把握してガードをかけているソースリストは問題ありませんが、ガードをかけていない場合はスタック領域をすべて消費し、スタック外に書き込もうとしたところをマイクロプロセッサに検出されてようやく実行が止まることになります。スタックの暴走を検出できる機構を備えている場合はこれで止まりますが、その機構が無い場合は大変なことになります。

　こうなると、どうしようもありません。ピボットを先頭に設定しているソースリストは、基本的に怪しいものと考えたほうが無難です。少ないデータ数でちょっと試して動いたからと言って、安易に使用してはいけません。

　ゼロクリアや、すべて定数のデータを流すと、ひどいめに会う例（日本語版 Wikipedia の外部リンク先）。次回の呼出し範囲にガードをかけているだけのもの。

void q_sort(int numbers[], int left, int right) {     int pivot, l_hold, r_hold;     l_hold = left;     r_hold = right;     pivot = numbers[left];     while (left < right)     {         while ((numbers[right] >= pivot) && (left < right))             right--;         if (left != right)         {             numbers[left] = numbers[right];             left++;         }         while ((numbers[left] <= pivot) && (left < right))             left++;         if (left != right)         {             numbers[right] = numbers[left];             right--;         }     }     numbers[left] = pivot;     pivot = left;     left = l_hold;     right = r_hold;     if (left < pivot)         q_sort(numbers, left, pivot-1);     if (right > pivot)         q_sort(numbers, pivot+1, right); }

処理速度の例とソースリスト

　処理速度の例とソースリストは、この次の「♪ドレミファソート」の中で記事を掲載します。

　ほとんどの紹介記事では、配列型で表記していますが、多くのＣコンパイラでは、ポインタ型で表記すると高速になることが多いです。

イントロソート

　英語版 Wikipedia によると、クイックソートが最悪計算量になるデータ列でも、イントロソートなら 200 分の１の時間でやってみせるさ。ということらしいです。一方、日本語版 Wikipedia によると、イントロソートなら、 1200 分の１でやってみせるさ。だそうです。