私の分類では、クイックソート(qsort)は10種類(qs0～qs9)あります。
#分類
分割要素をmとするとき、以下のように表すものとします。
キー値がmより小さい要素の並び → [小]
キー値がm以下の 要素の並び → [小＝]
キー値がmと同じ 要素の並び → [同]
キー値がm以上の 要素の並び → [大＝]
キー値がmより大きい要素の並び → [大]
どのqsortも後述する処理のあと、その処理を再帰的に繰り返します。
##qs1 [小＝][大＝] を作る
教科書にのっている普通のものです。
##qs0 [小＝][大＝] を作る キー値がmと同じ要素は移動なし
25年前、約2割のシステムが採用していました。
キー値が2値(男女など)のとき、O(n^2)の悲惨な計算時間となります。
##qs6 [小＝][大] または [小][大＝] を作る
qs7とほぼ同じ計算時間です。ただし、異常に長い計算時間はありません。
##qs7 [同][小][大][同] 、次に [小][同][大] を作る
現在の世界標準qsortの一つだと思います。(newlib系)
ただし、キー値が2値 && 要素が大きいとき、異常に長い計算時間となります。
(他に世界標準にはglibc系がありますが、これをqsortと呼んで良いかは疑問です)
##qs9 [小]～[同][大]、次に [小][小][大][同][大] とし、最後に [小][同][大] を作る
[小][同]～[大] となったら逆の動作をする。
比較関数の呼び出し回数、要素の移動回数ともに最小です。
標準のqsortより 1.04倍～3倍 高速です。
#お願い
現在、コンパイラ標準qsort と qs9 を比較するベンチマークテストを行っております。
http://ww51.tiki.ne.jp/~srr-cake/qsort/qs9/index.html
興味をお持ちの方はご協力頂けないでしょうか。
実行結果は、この記事のコメント欄にご記入下さい。
もし、お使いのコンパイラのライブラリがqs0を採用していれば、計算は終了しないかも知れません。その場合は、その旨をご記入下さい。