Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

クイックソートは、一つの値を軸に選び、残りを軸より小さいものと大きいものに分けることを繰り返す。本稿は、先頭の値を軸にする版と乱数で軸を選ぶ版の比べる回数を、乱れた入力と整列済みの入力で数え、平均の式と比較の下界と並べる。新しい定理も法則も主張しない。

第一に、乱れた入力では、先頭の軸でも平均は式どおりである。$n=100$・$500$・$1000$・$2000$ で比べる回数の平均は $656.9$・$4793.8$・$11051.2$・$24602.1$ で、式 $2(n+1)H_n-4n$ との比は $1.013969$・$0.997366$・$1.005943$・$0.994835$ だった（第2節）。

第二に、整列済みの入力では、先頭の軸は最も遅い。比べる回数はすべての組の数 $n(n-1)/2$ に一致し、$n=2000$ では $\mathbf{1999000}$ 回で、乱れた入力の平均の $\mathbf{81.253226}$ 倍だった（第3節）。

第三に、軸を乱数で選ぶと、整列済みの入力でも平均は式に戻る。整列済みの入力で $647.3$・$4795.0$・$10949.2$・$24744.2$ 回で、式との比は $0.99666$ から $1.000583$ だった（第3節）。

第四に、平均は比較の下界の一・三倍に届かない。下界 $\log_2 n!$ は $524.8$・$3767.4$・$8529.4$・$19053.0$ で、平均との比は $1.251798$ から $\mathbf{1.295660}$、係数の極限は $2\ln2=1.386294$ である（第4節）。

第五に、分離子は、手順が乱れを入力に頼るか、自分の中の乱数で作るかである。先頭の軸は入力が乱れていることに頼るので、整った入力が最悪になる。乱数の軸は乱れを自分で作るので、平均はどの入力でも同じになり、遅さは入力ではなく乱数の運の側に移る（第5節）。

キーワード：クイックソート、比較回数、平均計算量、最悪計算量、乱択アルゴリズム、比較の下界。

射程（何を示さないか）

新しい定理も法則も主張しない。クイックソート、その平均の比べる回数 $2(n+1)H_n-4n$、整列済みの入力で先頭の軸が $n(n-1)/2$ 回比べること、乱数で軸を選ぶと平均が入力によらないこと、比較の下界 $\log_2 n!$ は、いずれも既知である。実装の速さを論じない。記憶の読み書き、定数倍、再帰の深さは扱わない。数えるのは比べた回数だけである。分け方は一つに決めた。軸を先頭に置き、残りを一度ずつ軸と比べて分ける書き方（一回の分割で残りの数だけ比べる）を使う。ほかの軸の選び方や二本の軸は扱わない。乱数の運を上から押さえない。乱数の軸でも遅くなる確率がどれほど小さいかは主張しない。試行の平均を並べるだけである。既刊との関係：論文843 は、比べる回数の下界が入力ではなく答えの通り数で決まることを示した。ここでは、下界は入力によらないのに、先頭を軸にする手順の回数は入力の並びで $81.253226$ 倍も変わることを数える。論文759 は、同じ回数だけ比べても遅い記憶を読む回数が木の分岐で決まることを示した。ここでは記憶ではなく、比べる回数そのものが入力の並びと軸の選び方で変わることを数える。加えたのは、二つの版を二種類の入力で数えたこと、整列済みの入力の回数が $n(n-1)/2$ に一致することを確かめたこと、乱数の軸で整列済みの入力が式に戻ることを示したこと、平均と下界の比を並べたこと、分離子を「乱れを入力に頼るか、自分の乱数で作るか」に置いたことである。

1. 記法と問い

設定：長さ $n$ の列を、軸を先頭に置いて残りを一度ずつ軸と比べて分け、左右に同じことを繰り返して並べる。軸は先頭の値か、乱数で選んだ値を先頭に入れ替えたものとする。乱れた入力での平均の比べる回数と、比較の下界は次のとおりである。

$$C(n)=2(n+1)H_n-4n,\qquad H_n=\sum_{k=1}^{n}\frac1k,\qquad L(n)=\log_2 n!$$

検算では、$n=100$・$500$・$1000$ は $200$ 回、$n=2000$ は $60$ 回の試行で平均を取り、どの版も出力が整列していることを確かめた。

問い：クイックソートの遅さは、入力と軸の選び方の何で決まるか。

2. 乱れた入力

計算 2.1：先頭の軸・乱れた入力の平均と式。

観察 2.2　入力が乱れていれば、先頭の軸でも平均は式どおりである。乱れた入力の先頭は、乱数で選んだ値と同じように振る舞う。先頭の軸は、その乱れを入力から借りている。

3. 整列済みの入力

計算 3.1：整列済みの入力。

$n=2000$ で、先頭の軸の整列済みの回数は乱れた入力の平均の $\mathbf{81.253226}$ 倍だった。

観察 3.2　整った入力は、先頭の軸にとって最悪である。整列済みの列の先頭は最小の値なので、分けるたびに片側が空になり、残りの長さが一つずつしか減らない。軸を乱数で選ぶと、同じ整列済みの入力でも平均は式に戻った。

4. 下界との比

計算 4.1：比較の下界 $\log_2 n!$ は $524.8$・$3767.4$・$8529.4$・$19053.0$ で、先頭の軸・乱れた入力の平均との比は $1.251798$・$1.272445$・$\mathbf{1.295660}$・$1.291246$ だった。平均の $n\log_2 n$ の係数の極限は $2\ln2=1.386294$ である。

観察 4.2　平均は下界の一・三倍に届かず、入力によらない下界に近い。論文843 の下界は答えの通り数だけで決まり、入力の並びによらない。それに対し先頭の軸の回数は、同じ $n=2000$ で入力の並びにより $81.253226$ 倍変わる。

5. 分離子

観察 5.1　分離子は、手順が乱れを入力に頼るか、自分の中の乱数で作るかである。先頭の軸は入力の乱れを借りているので、乱れの無い整った入力でその借りが返せず、比べる回数がすべての組の数になる。乱数の軸は乱れを自分で作るので、平均はどの入力でも同じ式になり、遅くなるかどうかは入力ではなく乱数の運に移る。

観察 5.2　言わないこと。実装の速さ、記憶の階層、ほかの軸の選び方、乱数の軸で遅くなる確率の上限は扱わない。示したのは、先頭の軸が整った入力で最も遅く、軸を乱数で選ぶと平均がどの入力でも式に戻ることである。

6. 点呼と結び

1. $C(n)=2(n+1)H_n-4n$・$L(n)=\log_2 n!$（第1節）：平均と下界。
2. 乱れた入力で比 $0.994835$〜$1.013969$（計算 2.1）：式どおり。
3. 整列済みで $\mathbf{1999000}$ 回（計算 3.1）：$n(n-1)/2$。
4. 乱れた入力の $\mathbf{81.253226}$ 倍（計算 3.1）：最悪。
5. 乱数の軸で式との比 $0.99666$〜$1.000583$（計算 3.1）：入力によらない。
6. 平均÷下界 $\mathbf{1.295660}$ まで（計算 4.1）：極限 $2\ln2$。
7. 入力に頼るか、自分の乱数か（観察 5.1）：分離子・論文843・759。

結び：先頭を軸にするクイックソートは整った入力で最も遅く、軸を乱数で選ぶと平均の遅さは入力によらなくなる。乱れた入力では先頭の軸でも平均は式 $2(n+1)H_n-4n$ どおりだったが、整列済みの入力では比べる回数がすべての組の数になり、$n=2000$ で $81.253226$ 倍だった。軸を乱数で選ぶと、整列済みの入力でも平均は式に戻った。平均は入力によらない下界 $\log_2 n!$ の $1.295660$ 倍までにとどまった。分離子は、手順が乱れを入力に頼るか、自分の中の乱数で作るかである。既刊との位置：論文843 の入力によらない下界に対し、入力の並びで回数が変わる手順を並べ、論文759 の記憶の読み方とは別に、比べる回数そのものの入力への頼り方を数えた。正直に言えば、どの整列の手順が速いかは言わない。遅さを入力が決めるか乱数が決めるか、そこまでである。

参考文献

1. Hoare, C. A. R. (1962). Quicksort. The Computer Journal.
2. Sedgewick, R. (1977). The analysis of Quicksort programs. Acta Informatica.
3. 山岸勇輝 (2026). 『同じ回数だけ比べても、遅い記憶を読む回数は木の分岐で決まる』[論文759]. YOI: https://www.yamagishiyuuki.com/yoi/759 ・ DOI: 10.5281/zenodo.23015187
4. 山岸勇輝 (2026). 『比べる回数の下界は、入力ではなく答えの通り数で決まる』[論文843]. YOI: https://www.yamagishiyuuki.com/yoi/843

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「先頭を軸にするクイックソートは整った入力で最も遅く、軸を乱数で選ぶと平均の遅さは入力によらなくなる」［論文927］. YOI: https://www.yamagishiyuuki.com/yoi/927

@misc{yamagishi2026yoi927,
  author = {Yamagishi, Yuuki},
  title = {Quicksort with the First Element as Pivot Is Slowest on Sorted Input, and Choosing the Pivot at Random Makes Its Average Cost Independent of the Input},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/927},
  note = {Preprint, edition 1}
}