Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文927 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/927 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月11日 12:20 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969451・969456・969461・969490 に記録されました（2026年10月01日 23:00（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、乱れた入力では、先頭の軸でも平均は式どおりである。$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節）。

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

Abstract

Quicksort repeatedly chooses one value as a pivot and splits the rest into values smaller and larger than it.This paper counts the comparisons of a version using the first value as pivot and a version choosing the pivot at random, on shuffled and on sorted input, and sets them beside the average formula and the comparison lower bound.No new theorem or law is claimed.

First, on shuffled input, even the first-element pivot averages as the formula says: at $n=100$, $500$, $1000$ and $2000$ the mean comparisons were $656.9$, $4793.8$, $11051.2$ and $24602.1$, in ratios $1.013969$, $0.997366$, $1.005943$ and $0.994835$ to the formula $2(n+1)H_n-4n$ (Section 2).

Second, on sorted input, the first-element pivot is slowest: the comparisons equal the number of all pairs, $n(n-1)/2$: at $n=2000$, $\mathbf{1999000}$, which is $\mathbf{81.253226}$ times the shuffled-input mean (Section 3).

Third, with a random pivot, the average on sorted input returns to the formula: on sorted input it took $647.3$, $4795.0$, $10949.2$ and $24744.2$ comparisons, in ratios from $0.99666$ to $1.000583$ to the formula (Section 3).

Fourth, the average stays below 1.3 times the comparison lower bound: the lower bound $\log_2 n!$ is $524.8$, $3767.4$, $8529.4$ and $19053.0$, the ratio of the mean to it runs from $1.251798$ to $\mathbf{1.295660}$, and the limiting coefficient is $2\ln2=1.386294$ (Section 4).

Fifth, the separator is whether the procedure relies on the input for disorder or makes its own with random numbers: the first-element pivot relies on the input being disordered, so ordered input becomes its worst case. The random pivot makes its own disorder, so the average is the same for every input, and slowness moves from the input to the luck of the random numbers (Section 5).

Keywords: Quicksort, number of comparisons, average-case complexity, worst-case complexity, randomized algorithm, comparison lower bound

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/927/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/927 はいつも最新の版を指します）。

YOI の一覧へ