C
sort
アルゴリズム
ソート
クイックソート

最速のqsort(クイックソート) qs9 と ベンチマークテスト

より速い qsort( qs9 )

コンパイラ標準qsortより 1.04倍~3倍 高速なクイックソートです。
(64bitモードの極端なケースでは10倍高速)500行を超える大きなプログラムです。

コンパイラ標準qsort と qs9 を比較するベンチマークテストを作りました。
http://ww51.tiki.ne.jp/~srr-cake/qsort/qs9/index.html
に実施要領を記しました。ソースコードなどを含みます。

qs9より速いソート (qsort以外のソートも含む) があれば、
是非参考にして、改良したいと思っております。

ご興味のある方は、ベンチマークテストにご協力頂けないでしょうか

ベンチマークテストの出力例(一部)

「d=」キーの種類  「e=」要素数  「s=」要素の大きさ
「c=」比較関数の呼び出し回数  「T=」処理時間

----------- benchmark.txt begin ------- Z = 10 -----------
qsort d=-3 e=10000 s=8 0 R10000 M 0: 0 c=136796 ~ a=0 0 ~ T=20.32 203
qs9 d=-3 e=10000 s=8 0 R10000 M140:900 c=128188 ~ a=0 0 ~ T=18.72 187

qsort d=100 e=10000 s=20 0 R20000 M 0: 0 c=62887 ~ a=0 0 ~ T=36.46 182
qs9 d=100 e=10000 s=20 0 R20000 M140:900 c=60873 ~ a=0 0 ~ T=18.73 94

qsort d=2 e=10000 s=1000 10 R4000 M 0: 0 c=15020 ~ a=0 0 ~ T=28.89 722
qs9 d=2 e=10000 s=1000 10 R4000 M140:900 c=15053 ~ a=0 0 ~ T=8.74 218
================= benchmark.txt end ====================