newlib・glibcより高速なqsortクイックソート qs15 qs16

####newlib・glibcより高速なqsortクイックソート qs15 qs16

これまで長期間に渡り、実用的なqsortとして、newlib・glibc の qsort が
使われて来ました。そろそろより実用的で高速なqsortに置き換えても
良い時期ではないでしょうか。

newlib・glibc の qsort は、ソート条件（キー値の分布・要素数・要素サイズ）により
速い/遅いが入れ替わります。

ほどんど全てのソート条件で、 newlib・glibc のどちらよりも速い
qsort (qs15 , qs16) を作成しました。

ただし、意図的に最悪計算時間になるように作られたソート対象配列では
glibc の qsort が最速(または、比較関数の呼び出し回数が最小)となります。なぜなら、
glibc の qsort の実体はマージソートだからです。

qs15・qs16は、以前に作成したqs12・qs13より
コンパクト(バイナリコードで半分の大きさ）になっています。

qs15は、基本的にはクイックソート
qs9 (https://qiita.com/t-kawa/items/99408891b18bd1f87ae6) として動きます。
ただし、間接ソートが速いと予測したときは、間接ソートを行います。
間接ソートとは、各要素へのポインタ配列を作り、これをソートすることです。

qs16は、qs15・直接mps・間接mpsから適切な手法を予測してソートを行います。
mpsとは、サンプル(m個)をソートして、区間(2m+1個)のそれぞれの先頭位置を計算して、
その区間内の位置に各要素を移動して、最後にソートが必要な区間(m+1個)をソートします。

newlib・glibc・qs15・qs16の比較回数・実行時間を以下に示します。
qs_glibcは、glibcのqsortを実験用に改造したものです。
使用したプログラムは https://github.com/kawamura1953/quick-sort にあります。




```
----------------- benchmark.txt begin -------------------- 
 
キー種別:同値なし　要素数:1万個　要素サイズ:8,80,1000byte 
qsort    d=-3 e=10000 s=8 R5000 M000:000:000:0: c=136795  683975303 T=10.22  204 
qsnewlib d=-3 e=10000 s=8 R5000 M000:000:000:0: c=136795  683975303 T=10.42  208 
qs_glibc d=-3 e=10000 s=8 R5000 M000:000:000:0: c=120451  602257294 T=12.15  243 
qs15c2   d=-3 e=10000 s=8 R5000 M120:580:180:0: c=128064  640321766 T=9.66   193 
qs16e2   d=-3 e=10000 s=8 R5000 M120:580:180:0: c=128064  640321766 T=9.64   193 
 
qsort    d=-3 e=10000 s=80 R5000 M000:000:000:0: c=136795  683975303 T=14.27  285 
qsnewlib d=-3 e=10000 s=80 R5000 M000:000:000:0: c=136795  683975303 T=14.21  284 
qs_glibc d=-3 e=10000 s=80 R5000 M000:000:000:0: c=120451  602257294 T=16.38  328 
qs15c2   d=-3 e=10000 s=80 R5000 M120:580:180:0: c=128064  640321766 T=11.36  227 
qs16e2   d=-3 e=10000 s=80 R5000 M120:580:180:0: c=128064  640321766 T=11.37  227 
 
qsort    d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=136826  136826241 T=16.04 1604 
qsnewlib d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=136826  136826241 T=16.11 1611 
qs_glibc d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=120450  120450635 T=7.82   782 
qs15c2   d=-3 e=10000 s=1000 R1000 M120:580:180:0: c=128086  128086595 T=7.41   741 
qs16e2   d=-3 e=10000 s=1000 R1000 M120:580:180:0: c=128086  128086595 T=7.49   749 
 
キー種別:100種　要素数:1万個　要素サイズ:8,80,1000byte 
qsort    d=100 e=10000 s=8 R10000 M000:000:000:0: c=62873   628731716 T=8.74    87 
qsnewlib d=100 e=10000 s=8 R10000 M000:000:000:0: c=62873   628731716 T=9.25    92 
qs_glibc d=100 e=10000 s=8 R10000 M000:000:000:0: c=120211 1202115137 T=22.04  220 
qs15c2   d=100 e=10000 s=8 R10000 M120:580:180:0: c=60846   608464923 T=8.72    87 
qs16e2   d=100 e=10000 s=8 R10000 M120:580:180:0: c=60846   608464923 T=8.58    86 
 
qsort    d=100 e=10000 s=80 R10000 M000:000:000:0: c=62873   628731716 T=14.52  145 
qsnewlib d=100 e=10000 s=80 R10000 M000:000:000:0: c=62873   628731716 T=14.82  148 
qs_glibc d=100 e=10000 s=80 R10000 M000:000:000:0: c=120211 1202115137 T=29.34  293 
qs15c2   d=100 e=10000 s=80 R10000 M120:580:180:0: c=60846   608464923 T=10.86  109 
qs16e2   d=100 e=10000 s=80 R10000 M120:580:180:0: c=60846   608464923 T=10.70  107 
 
qsort    d=100 e=10000 s=1000 R2000 M000:000:000:0: c=62947   125895777 T=24.94 1247 
qsnewlib d=100 e=10000 s=1000 R2000 M000:000:000:0: c=62947   125895777 T=25.05 1253 
qs_glibc d=100 e=10000 s=1000 R2000 M000:000:000:0: c=120212  240424496 T=14.79  739 
qs15c2   d=100 e=10000 s=1000 R2000 M120:580:180:0: c=60879   121759817 T=12.26  613 
qs16e2   d=100 e=10000 s=1000 R2000 M120:580:180:0: c=61391   122782892 T=11.86  593 
 
キー種別:2種　要素数:1万個　要素サイズ:8,80,1000byte 
qsort    d=2 e=10000 s=8 R20000 M000:000:000:0: c=15020   300410541 T=4.07   20 
qsnewlib d=2 e=10000 s=8 R20000 M000:000:000:0: c=15020   300410541 T=4.43   22 
qs_glibc d=2 e=10000 s=8 R20000 M000:000:000:0: c=94725  1894516279 T=30.65 153 
qs15c2   d=2 e=10000 s=8 R20000 M120:580:180:0: c=15052   301043181 T=3.68   18 
qs16e2   d=2 e=10000 s=8 R20000 M120:580:180:0: c=15052   301043181 T=3.73   19 
 
qsort    d=2 e=10000 s=80 R20000 M000:000:000:0: c=15020   300410541 T=10.11  51 
qsnewlib d=2 e=10000 s=80 R20000 M000:000:000:0: c=15020   300410541 T=10.44  52 
qs_glibc d=2 e=10000 s=80 R20000 M000:000:000:0: c=94725  1894516279 T=42.70  213 
qs15c2   d=2 e=10000 s=80 R20000 M120:580:180:0: c=15052   301043181 T=4.51   23 
qs16e2   d=2 e=10000 s=80 R20000 M120:580:180:0: c=15052   301043181 T=4.46   22 
 
qsort    d=2 e=10000 s=1000 R3000 M000:000:000:0: c=15020    45060726 T=22.21  740 
qsnewlib d=2 e=10000 s=1000 R3000 M000:000:000:0: c=15020    45060726 T=22.07  736 
qs_glibc d=2 e=10000 s=1000 R3000 M000:000:000:0: c=94732   284197358 T=19.47  649 
qs15c2   d=2 e=10000 s=1000 R3000 M120:580:180:0: c=15084    45253464 T=6.65   222 
qs16e2   d=2 e=10000 s=1000 R3000 M120:580:180:0: c=15084    45253464 T=6.61   220 
 
 
キー種別:10種　要素数:1万,10万,100万個　要素サイズ:400byte 
qsort    d=10 e=10000 s=400 R2000 M000:000:000:0: c=30277    60554039 T=7.13  356 
qsnewlib d=10 e=10000 s=400 R2000 M000:000:000:0: c=30277    60554039 T=7.36  368 
qs_glibc d=10 e=10000 s=400 R2000 M000:000:000:0: c=116416  232833027 T=10.08 504 
qs15c2   d=10 e=10000 s=400 R2000 M120:580:180:0: c=29649    59299425 T=4.63  232 
qs16e2   d=10 e=10000 s=400 R2000 M120:580:180:0: c=29712    59424938 T=4.27  214 
 
qsort    d=10 e=100000 s=400 R200 M000:000:000:0: c=301637   60327445 T=9.59   4796 
qsnewlib d=10 e=100000 s=400 R200 M000:000:000:0: c=301637   60327445 T=9.22   4610 
qs_glibc d=10 e=100000 s=400 R200 M000:000:000:0: c=1479728  295945709 T=16.25 8128 
qs15c2   d=10 e=100000 s=400 R200 M120:580:180:0: c=294954   58990860 T=5.32   2660 
qs16e2   d=10 e=100000 s=400 R200 M120:580:180:0: c=292624   58524925 T=5.12   2558 
 
qsort    d=10 e=1000000 s=400 R20 M000:000:000:0: c=2980287   59605743 T=9.47    47345 
qsnewlib d=10 e=1000000 s=400 R20 M000:000:000:0: c=2980287   59605743 T=9.56    47815 
qs_glibc d=10 e=1000000 s=400 R20 M000:000:000:0: c=17952145  359042905 T=21.32 106615 
qs15c2   d=10 e=1000000 s=400 R20 M120:580:180:0: c=2940213   58804262 T=5.58    27925 
qs16e2   d=10 e=1000000 s=400 R20 M120:580:180:0: c=2910960   58219214 T=5.22    26125 
 
=================  benchmark.txt end  ==================== 
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です 
 
```




qsortのベンチマークテストの要領

１．github.com/kawamura1953/quick-sort から次の７つのファイルをダウンロードする。

    qs15c2.c     
    qs16e2.c     
    mm88k.c.c    
    qsnewlib.c   
    qs_glibc.c   
    main_prog.c  
    benchmark.sh 


２．benchmark.sh を実行する。実行結果は benchmark.txt へ書き込まれる。

　　main_prog.c は benchmark.sh の中でコンパイル・実行されます。
　　これの引数と出力の説明は、Readme2.txtを参照。


３．その他のファイル

    Readme.txt       : このファイル
    Readme2.txt      : より詳細な説明
    bench-sample.txt : ベンチマークテスト結果の例