以前報告した２つのクイックソート ss18 と qs19 を改良したので報告します。

主な変更点は、安全性のための変更と、再帰呼び出しへの書き換えです。

qsort20(qs20)(qs19を改良) は、従来のqsortに比べて 1.1～2 倍高速です。そして、安全です。

sqsort(ss21)(ss18を改良) は、timsort よりも 1.7～5 倍高速です。そして、安定・安全です。

以下では、
安定とは、「キー値が同じ要素は、ソートの前後でその順序を維持する」こととします。
安全とは、「悪意のある配列により、異常に長いソート時間を発生させることが不可能」
　　　　　　　　　なこととします。

qsort20・sqsort では「安全」を実現するために、
clock()関数を再現性のない乱数発生器として使用し、乱数を用いてピボットを決定します。
これにより、理論上の最悪計算時間$O(n^2)$は変化しませんが、
「悪意のある配列を作ることは不可能」となります。

ただし、qsort20 において、安全性の機能を発動するための
大域変数 _QS_RNDM の初期値は 0 です。
このため、_QS_RNDM=1; を実行するまで、この機能は発動しません。
なぜなら、この機能を発動すると、同じ内容の配列をソートしても、
ソート結果が異なることがあるからです。
この現象は、キー値が同じ要素を持つ配列で現れます。
そのため、プログラムが「安全性」を必要とする場合にのみ、
qsort20 を呼び出すプログラムのデバッグが終わったあとで、
_QS_RNDM=1; を追加して下さい。
追加の後、プログラムの動作が変わるようであれば、
プログラムに問題があることになります。

一方、sqsort では、常にこの機能が発動しています。
なぜなら、sqsort は「安定性」があるので、
キー値が同じ要素を持つ配列をソートしても、常にソート結果が同じだからです。
　

従来のqsortとtimsortを含めた４種類のソートを比較すると次の表のようになります。

	timsort	sqsort	qsort20	従来qsort
速さ	△	◎	◎	○
作業領域	△	△	◎	◎
安定性	○	○	×	×
安全性	◎	○	○	×
大きさ	×	○	○	◎

qsort20 のソースコード・ベンチマークプログラムは
　　　　https://github.com/kawamura1953/qsort20 　　にあります。

sqsort・timsort のソースコード・ベンチマークプログラムは
　　　　https://github.com/kawamura1953/sqsort 　　にあります。

以下に、上の４種類のベンチマークテストの一部を掲載します。
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です。

　　キー:同値なし 要素:1万個　要素サイズ:8,20,80,1000byte 
my_qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136763  547054643 T=3.75    94 
qsort20  d=-3 e=10000 s=8 R4000 M120:580:000:0: c=128053  512215278 T=3.35    84 
sqsort   d=-3 e=10000 s=8 R4000 M120:009:018:0: c=141431  565726225 T=3.19    80 
timsort  d=-3 e=10000 s=8 R4000 M000:000:000:0: c=120391  481564348 T=5.41   135 
 
my_qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136748  410244182 T=4.73  158 
qsort20  d=-3 e=10000 s=20 R3000 M120:580:000:0: c=128047  384143863 T=2.91   97 
sqsort   d=-3 e=10000 s=20 R3000 M120:009:018:0: c=141452  424357003 T=3.09  103 
timsort  d=-3 e=10000 s=20 R3000 M000:000:000:0: c=120392  361177167 T=10.73 358 
 
my_qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136748  410244182 T=3.62  121 
qsort20  d=-3 e=10000 s=80 R3000 M120:580:000:0: c=128047  384143863 T=3.20  107 
sqsort   d=-3 e=10000 s=80 R3000 M120:009:018:0: c=141420  424261003 T=3.36  112 
timsort  d=-3 e=10000 s=80 R3000 M000:000:000:0: c=120392  361177167 T=13.98 466 
 
my_qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136776   82066150 T=3.52   586 
qsort20  d=-3 e=10000 s=1000 R600 M120:580:000:0: c=128099   76859601 T=1.81   302 
sqsort   d=-3 e=10000 s=1000 R600 M120:009:018:0: c=141426   84856124 T=1.70   284 
timsort  d=-3 e=10000 s=1000 R600 M000:000:000:0: c=120391   72234833 T=12.81 2135