sqsortの特徴は、同じキー値(県名・男女など)が現れる場合に極めて高速なことです。
また、マージソート的な部分がないにもかかわらず、安定性があることです。
以下では、
「安定」とは、「キー値が同じ要素は、ソート前の順序をソート後も維持する」こととします。
「安全」とは、「悪意のある配列により、異常に長いソート時間を発生させることが不可能」
なこととします。
sqsort では「安全」を実現するために、
clock ( ) 関数を再現性のない乱数発生器として使用し、ピボットの候補を決定します。
これにより、理論上の最悪計算時間 $O(n^2)$ は変化しませんが、
「悪意のある配列を作ることは不可能」となります。
sqsort は大雑把にいうと、対象配列 ( ptr ) と補助配列 ( ptr2 ) で
次のような移動(Ａ,Ｂ)を繰り返します。
ptr2:............... → ptr2:332223....77787 → ptr2:332223....77787
ptr :357358257257237 Ａ ptr :5555........... Ｂ ptr :......5555.....
sqsort・timsort の ソースコード・ベンチマークプログラム は
http://ww51.tiki.ne.jp/~srr-cake/qsort/ssc18/ にあります。
sqsort ( 約350行 .oファイル約12800byte ) は、
timsort ( 約1300行 .oファイル約31400byte ) よりかなりコンパクトです。
qsortを含めた３種類のソートを比較すると次の表のようになります。
| timsort | sqsort | qsort 非安定 | |
|---|---|---|---|
| 速さ | △ | ◎ | ◎ |
| 作業領域 | △ | △ | ◎ |
| 安定性 | ○ | ○ | × |
| 安全性 | ◎ | ○ | × |
| サイズ | × | ○ | ◎ |
処理時間を測定したもの ( benchmark.txt ) を以下に記載します。
各行の最後の数値がソート１回あたりの処理時間です。
48行目で my_qsort より sqsort が少し遅くなっていますが、
これは、sqsortの「安定性」実現のために、余分な要素の移動が起きたためです。
----------------- benchmark.txt begin --------------------
キー:同値なし 要素:1万個 要素サイズ:8,20,80,1000byte
my_qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136798 547192609 T=3.77 94
timsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=120390 481561920 T=5.38 134
sqsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=141438 565754586 T=3.27 82
my_qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136804 410413695 T=4.73 158
timsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=120390 361170762 T=10.73 358
sqsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=141434 424304000 T=3.08 103
my_qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136804 410413695 T=3.61 120
timsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=120390 361170762 T=13.92 464
sqsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=141416 424249151 T=3.36 112
my_qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136845 82107153 T=3.48 581
timsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=120389 72233808 T=12.56 2094
sqsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=141351 84810864 T=1.69 281
キー種別:100種 要素:1万個 要素サイズ:8,20,80,1000byte
my_qsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62893 377363710 T=2.42 40
timsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=103239 619435932 T=7.33 122
sqsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62388 374330081 T=2.23 37
my_qsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62926 188780724 T=2.52 84
timsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=103239 309719470 T=8.59 286
sqsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62402 187208373 T=1.74 58
my_qsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62922 251691334 T=2.40 60
timsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=103240 412961519 T=15.39 385
sqsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62376 249505124 T=2.56 64
my_qsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62919 31459751 T=2.17 434
timsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=103239 51619835 T=9.62 1925
sqsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62401 31200583 T=1.19 237
キー種別:2種 要素:1万個 要素サイズ:8,20,80,1000byte
my_qsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=15020 180242977 T=1.16 10
timsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=45262 543150430 T=7.89 66
sqsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=15014 180176778 T=1.00 8
my_qsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=15020 105142708 T=2.20 31
timsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=45263 316841085 T=8.08 115
sqsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=15046 105326276 T=0.95 14
my_qsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=15020 90123066 T=1.20 20
timsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=45263 271579105 T=9.36 156
sqsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=15015 90091994 T=1.72 29
my_qsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=15021 6008462 T=0.97 242
timsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=45265 18106265 T=3.95 988
sqsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=15010 6004395 T=0.77 192
キー:同値なし 百～百万要素 要素サイズ:200byte
my_qsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=644 128893028 T=1.67 1
timsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=538 107623993 T=4.89 2
sqsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=691 138210336 T=1.38 1
my_qsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10064 140901071 T=1.67 12
timsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=8682 121560507 T=5.39 39
sqsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10530 147423146 T=1.16 8
my_qsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=136826 136826241 T=1.59 159
timsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=120389 120389545 T=6.25 625
sqsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=141353 141353954 T=1.17 117
my_qsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1727630 103657844 T=1.50 2498
timsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1534821 92089290 T=5.00 8333
sqsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1777877 106672678 T=1.62 2708
my_qsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=20971928 146803502 T=2.14 30557
timsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=18640815 130485706 T=7.12 101786
sqsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=21374068 149618482 T=2.70 38629
================= benchmark.txt end ====================
my_qsort：ベンチマークテスト実行の計算機上の C ライブラリの qsort
timqsort：https://github.com/patperry/timsort/ の timsort
sqsort ：今回公開した sqsort
d=キー種類 e=要素数 s=要素サイズ R繰返し回数 c=比較回数/R T=処理秒数
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です