開発に至る経緯
javaのsortとしてTimSortが採用されたと聞いた。TimSortはマージソートが元に
なっているので速度的に問題があると思った。そこで、クイックソートを元にした
Sqsort https://qiita.com/t-kawa/items/4be381efb74d44fc991c を開発した。
初代のSqsortは、TimSortより速く、安定だが、最悪計算時間で負けていた。
そこで「乱数を用いてピボットを選択」を導入して、最悪計算時間の改善を図った。
これにより、Sqsort の最悪計算時間が O(n^2) になる確率は
実用上ほぼ０であると考える。これを解説するのが本稿の目的である。
本稿は証明ではなく、「実用上問題ない」ことの解説である。
理想的な解決方法（解析的方法）
「乱数でピボットを選択したqsort」は
最悪計算時間や安全性の問題を、確率の問題として扱おうとしている。
ユニーク乱数による長さ n の配列をクイックソート(qsort)するとき、
要素の比較回数の平均は C × n × log2(n) である。
ソート１回における比較回数が C × n × log2(n) の a 倍 以上 になる確率 P ( n, a ) は
どのような数式になるのだろうか？
この問題に解析的な答えがあるらな、P( 1000000, 2.0 ) などを手(て)計算して、
その値が十分に小さいこと示せば、「実用上問題ない」ことを示せたことになる。
しかし、解析的な答えは作成不可能のように思われた。
（「ユニーク乱数による配列」とは、ソートキーに同じものが１つもなくて、
キーの並びを乱数で決定した配列のことである。）
シミュレーションによる解決方法
qsortの最悪計算時間には、次の3つの場合がある。
１．n! 通りある要素の並びから選ばれた配列が、本当に本当に運悪く最悪である場合。
２．"並び" と ピボット選択方法 の相性が悪い場合。（並びが既昇順＋ピボット先頭固定など）
３．特定のqsortアルゴリズムを攻撃するために作成された「悪意のある配列」である場合。
この内、「１．」は qsort の本質的な特徴であり、改善することはできない。
一方、「ピボットの位置を乱数を用いて決定」することにより
「２．」と「３．」の出現確率は、「１．」と同じ出現確率になると考えられる。
以下では「乱数でピボットを選択」を導入した Sqsort について解説する。
これにより、「１．２．３．」全ての場合で最悪計算時間を実用上 O(n×log(n)) にできると考える。
ソートキーがユニーク乱数で、要素数が n=1000、ソートの繰返し回数が R=1万回 のとき、
1万回中の i 回目のソートにおける"要素の比較関数"の呼出し回数(以後,比較回数)を ci とする。
また、計算時間は ci に比例し、ci の平均は n×log(n)（＝g）に比例するものとする。
以上を前提とするとき、ci/g (i=1,2,…,1万) は i や n が変化してもほぼ一定の値を取る（1.0に近い値）。
しかし、かなりの変動がある。R が大きいほど変動幅も大きくなる。
c1/g, c2/g, …, c1万/g を計算して ci/g の分布を取ると次のようになった。(n=1000, R=10000の場合)
| ci/g区間 | [0.9,1.0) | [1.0,1.1) | [1.1,1.2) | [1.2,1.3) | [1.3,1.4) | [1.4,1.5) | [1.5,1.6) |
|---|---|---|---|---|---|---|---|
| 出現頻度 | 434 | 4907 | 3727 | 825 | 92 | 14 | 1 |
これを n=1000、R=1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10 について計算したのが表１である。
ここで 1e4 は 10^4 を表している。 @1.2 は区間 [1.2,1.3) を表している。
| ci/g区間 | @0.8 | @0.9 | @1.0 | @1.1 | @1.2 | @1.3 | @1.4 | @1.5 | @1.6 | @1.7 | @1.8 | @1.9 | @2.0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| R=1e3 | 47 | 454 | 397 | 89 | 12 | 1 | |||||||
| R=1e4 | 434 | 49e2 | 37e2 | 825 | 92 | 14 | 1 | ||||||
| R=1e5 | 45e2 | 48e3 | 38e3 | 82e2 | 10e2 | 98 | 3 | 1 | |||||
| R=1e6 | 2 | 46e3 | 49e4 | 38e4 | 82e3 | 98e2 | 827 | 44 | 4 | # | |||
| R=1e7 | 20 | 45e4 | 49e5 | 37e5 | 82e4 | 99e3 | 86e2 | 555 | 32 | 3 | # | ||
| R=1e8 | 250 | 45e5 | 49e6 | 37e6 | 82e5 | 99e4 | 85e3 | 59e2 | 299 | 13 | 1 | ||
| R=1e9 | 23e2 | 45e6 | 49e7 | 37e7 | 82e6 | 99e5 | 85e4 | 58e3 | 33e2 | 158 | 10 | 1 | |
| R=1e10 | 24e3 | 45e7 | 49e8 | 37e8 | 82e7 | 99e6 | 85e5 | 58e4 | 33e3 | 1513 | 59 | 5 | # |
表１ n=1000 での比較回数のバラツキ(ci/g)の分布 (空白欄は"0") (行の横合計=R)
表１の各行の右端の "1" に着目する。（ "#" は "1" の出現が予測される位置である。）
ソートをR回繰返したとき、"1" は比較回数(バラツキci/g)が最大となる区間を表している。
R=1e4=1万の場合は、@1.5 の下に "1" があるので
ソートを1万回(R)繰返した場合、比較回数 @1.5 × n × log(n) 回を必要とするソートが
1万回(R)の中に平均で約 "1" 回あることを示している。
逆に言うと、「 @1.5 の変動を目撃したければ約1万回の繰返し(R)を覚悟しろ」と言うことである。
表１の "1"（"#"を含む）に着目し、8個ある "1" を出現させるための繰返し回数(R)
を１行で表すと次のようになる。(n=1000の場合)
| ci/g区間 | @1.4 | @1.5 | @1.6 | @1.7 | @1.8 | @1.9 | @2.0 |
|---|---|---|---|---|---|---|---|
| 繰返し回数R | 1e3 | 1e4 | 1e5 | 1e6 | 1e7～1e8 | 1e9 | 1e10 |
さらに、これを n=1000=1e3 だけでなく n=1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8
について計算したのが表２である。
| ci/g区間 | @1.4 | @1.5 | @1.6 | @1.7 | @1.8 | @1.9 | @2.0 | @2.1 | @2.2 | … | @2.6 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| n=1e2 | 1e3 | 1e4 | 1e5 | 1e6 | 1e7 | 1e7 | 1e89 | 1e10 | 1e11 | … | 予想 |
| n=1e3 | 1e3 | 1e4 | 1e5 | 1e6 | 1e78 | 1e9 | 1e10 | … | (1e16) | ||
| n=1e4 | 1e4 | 1e4 | 1e56 | 1e78 | 1e9 | … | (1e17) | ||||
| n=1e5 | 1e3 | 1e35 | 1e67 | 1e8 | … | (1e18) | |||||
| n=1e6 | 1e3 | 1e4 | 1e57 | ※ | … | (1e18) | |||||
| n=1e7 | 1e3 | 1e45 | 1e67 | … | (1e18) | ||||||
| n=1e8 | 1e34 | 1e5 | 1e6 | … | (1e18) |
表２ 各n,各区間に対応する "1" が出現するはずの繰返し回数(R) (@2.6の列は予想値)
1e35 は 10^3～10^5 を表している。ただし、1e1* は 10^1* を表している。
この表の値を qsort で計算しようとすると時間がかかり過ぎて計算できない。
「ソートせずに比較回数(ci)だけ」を計算するプログラムsss(約100倍高速)
http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/main_sss.c を作成・使用している。
この表の空白欄は "0" ではない。sssでも時間がかかり過ぎて計算できない部分である。
計算できない部分（結論）
計算できない部分も予想することはできる。表２の@2.6の列は予想値である。
ただし、表２の "※" などの位置に小さな値(1e5など)が現れると予想はできなくなってしまう。
@2.6列はあくまで予想であって根拠はない。
n=1e3 行 で @2.6 列 の欄の予想回数(R)は、1e16 以上と予想される。
予想回数R(1e16回) のどの 比較回数(ci) も概ね n × log(n) 以上である。
よって、この場合の "総" 比較回数は
予想回数R × n × log(n) ≒ 1e16 × 1000 × 10 ＝ 1e20
以上となる。
比較1回あたりの計算時間を10ナノ秒とすると、
予想回数実行に必要な計算時間 ＝ 1e20比較 × 10ナノ秒／比較 ≒ 3万年
以上となる。
一般に、qsortの平均比較回数(＝C×n×log(n))の C は 1.2～1.3 である。
@2.6 は C のほぼ２倍である。そのため、偶然に平均の２倍の計算時間に
遭遇するには、n=1000 の場合で "３万年" 待つことが "予想" される。
計算機の故障頻度などを考慮すれば、３万年に１度の現象はほぼ出現しない現象といえる。
そして、仮に出現したとしても、平均の "たった" ２倍の計算時間で正常にソートは終了する。
このことは、「１．」の n! がいかに 大きな数 で、
計算時間 O(n^2) を必要とするケースがいかに 稀 であるかを示している。
以上により、「乱数でピボットを選択したqsort」の最悪計算時間は
O(n^2) でなく、O(n×log(n))として実用上問題ないと思われる。
悪意のある配列について
「悪意のある配列」に対しても「乱数でピボットを選択したqsort」は有効である。
与えられた配列がたとえ「悪意のある配列」であったとしても、
乱数でピボットを選択することにより、「悪意のある並び順」が無効になるからである。
乱数を用いた Sqsort と qsort のソート結果の再現性
Sqsort はその処理の先頭で nanoTime() を１度だけ呼び出して乱数を作っている。
そのため、Sqsortの実行ごとに異なる乱数でピボットを選択する。
その結果、２つの同じ配列をソートしたとき、２つの"処理過程"は同じにはならない、
しかし、Sqsortは "安定" なソートなので "処理結果"(２つの配列) は同じになる。（再現性あり）
一方、従来のqsortに「乱数でピボットを選択」を導入した場合、
２つの同じ配列をソートしたとき、"処理結果" は異なる。（再現性なし）
qsortが "非安定" なため、ソートキーが同じ要素の最終位置が変動するからである。
「最悪計算時間」や「悪意のある配列」に関して、このqsortは良好な動作をする。
しかし、この再現性のなさは悪い動作といえる。