ソートアルゴリズム対決

同じ入力で競い合う2つのアルゴリズムをステップごとに追う — 比較回数、交換回数、計算量

インタラクティブシミュレーションを読み込んでいます...

ビッグオーだけでは語れない 🖖

バブルソートは最悪の場合、正確にn(n−1)/2回の比較を行う — n=64なら約2,000回。毎回のパスは早期終了なしに未ソート領域全体を走査しなければならない。クイックソートの分割はピボットを最終位置に配置し、問題を2つの部分問題に分割する。各再帰レベルはO(n)の作業をO(log n)レベルにわたって行い、合計O(n log n)となる。落とし穴は、ピボットが常に一方の端に来る場合 — 例えば最後の要素をピボットにしたソート済み入力 — 分割がサイズn−1、n−2、…と続くn個の部分問題に退化し、合計するとO(n²)になることだ。ここで使われている中央要素ピボットはこれを回避するため、逆順の入力でも高速なままである。重複の多いデータは興味深いケースだ。多くの要素がピボットと等しい場合、同じ値同士の交換は無駄な作業になり、二次的な挙動に近づく可能性がある。ビッグオーは成長のクラスを教えてくれるが、定数、入力への感度、キャッシュの挙動が、実際に採用すべきアルゴリズムを決定する。

秒ではなくステップを数える理由 🖖

このレースは各アルゴリズムを、ストップウォッチではなく比較と交換の回数で評価します。実際の経過時間はCPUやブラウザ、同時に動いている他のプログラムに左右されるため、同じコードでも機械によって速くも遅くも見えてしまいます。操作回数を数えれば、実際の仕事量を明快かつ再現可能に測れます。同じ入力なら必ず同じ回数になるので、ハードウェアではなくアルゴリズムそのものを比較できるのです。

クイックソートはロシア語翻訳から生まれた 🖖

トニー・ホーアは1959年、モスクワに留学中、機械翻訳プロジェクトに取り組む中でクイックソートを考案しました。ロシア語の文を辞書で引くには、まず単語をアルファベット順に並べる必要があり、当時の標準的な方法は絶望的に遅かったのです。ピボットを軸に分割する彼の解決策は、史上最も使われるアルゴリズムの一つになりました。ここで競う棒グラフは、計算ではなく言語の問題から始まった発想をたどっているのです。

全プロセスの詳細解説

逆順の64要素におけるバブルソートの正確な交換回数の予測 7 ステップ
逆順プリセット（64個の要素、大きい順）でレースを実行してください。バブルソートの交換回数を計算量のオーダーではなく 正確に 予測し、隣接要素の交換を行うどのようなアルゴリズムもその記録を破ることができない理由を述べてください。
1. 転倒（inversion）とは、相対的な順序が逆になっている対（ペア）のことである。逆順の入力はその極端な例であり、すべての i < j について手前の要素の方が大きいため、あらゆる対が転倒しており、その総数が転倒数となる。何も移動しないうちにこの数を求めておく。実は、これこそが問題のすべてなのである。
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. バブルソートは、隣接する要素が順序通りでない場合にのみ、その隣接要素同士を交換する。このような交換はその1つの対を解消し、他の対には一切影響を与えない。移動する2つの要素は、それら以外のすべての要素との相対的な位置関係を維持するからである。1回の交換で解消される転倒は常に1つであり、2つになることも、0になることもない。
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. ソート済みとは、転倒が0個であることを意味する。2,016から始めて1回の交換ごとに正確に1個ずつ減らしていく以上、抜け道はない。交換回数は 一義的に決まる のである。パネルには 2,016 回の交換と表示されるが、これは最悪のケースの界（バウンド）ではなく、恒等的な事実（等式）である。
  
  $S = I_{0} - 0 = 2, 016$
4. 比較回数は別のカウントであり、ここではたまたま一致している。パス i では j = 0 … 62 − i をスキャンするため、合計は 63 + 62 + ⋯ + 1 となり、バブル最悪ケース n(n−1)/2 の行に示されている 2,016 と同じになる。両方の回数が等しいということは、あらゆる比較で転倒が検出されたことを意味し、これこそがここでの「最悪のケース」の意味である。各パネルのタイトルの下にあるカウンターは比較1回につき1ステップ、交換1回につき1ステップをカウントするため、開始前は ステップ 0 / 4,032 と表示され、› ボタンを1回クリックするごとにこれらのステップが正確に1つ消費される。タイトルの横にある O(n²) はラベルであって、集計値ではない。
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. ここでステップ2を一般化する。これこそがクイックソートが利用している仕組みだからである。d 離れた位置にある2つの要素を交換しても、その範囲の外側にある要素と形成されるすべての対の合計には一切影響を与えない。そのような要素は他方の端と再比較され、2つの比較が入れ替わるだけで、その寄与は変化しないからである。変化し得るのは、その対自体と、各端が形成する 2(d − 1) 個の対（その間にある d − 1 個の要素との対）である。1回の交換で解消できる転倒は最大でも 2d − 1 個であり、d = 1 と置けばステップ2の単一の転倒解消へと還元される。
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. クイックソートの最初の分割では、中央の要素をピボット a[31] = 33 として選択し、(0, 63)、(1, 62)、…、(31, 32) の交換を行う。これは距離 63、61、…、1 での 32 回の交換である。ステップ5により、これらの合計効果の上限は 2,016 個の転倒と抑えられるが、この1回のパスで配列は完全にソートされるため、正確に 2,016 個が解消されたことになる。この上限は等号で達成されており、32 回の交換のそれぞれが自身の最大効果を達成したのである。
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. したがって、この2つのアルゴリズムは巧妙さを競っているのではなく、一度に届く距離（リーチ）を競っているのである。クイックソートの表示された 334 回の比較と 64 回の交換の合計は、カウンターの 398 に一致する。そして、これらの交換のうち実際に要素を移動させるのは 32 回のみであり、残りの 32 回はすでに整列している区間においてピボット自身と交換されているだけである。また、334 という比較回数も 下回って おり、表示されている n·log₂n の参照値 384 よりも少なくなっている。逆順の列の中央要素はその中央値（メディアン）であり、すべての分割が均等になるからである。
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
解答

2,016 回の交換と 2,016 回の比較 — カウンター上の 4,032 ステップ。 そして、2,016 という数値はバブルソート固有の事実ではなく、アルゴリズムの一群全体に対する下限（フロア）である。隣接する 要素の交換のみに制限された任意のアルゴリズム — 挿入ソート、カクテルソート、ノームソート、あるいはまだ誰も書いていないアルゴリズム — は、ステップ2より1回の交換につき最大1つの転倒しか解消できない。そのため、それらすべてがこの入力に対して少なくとも 2,016 回の交換を必要とし、不器用だからではなく機能するモデルの制約によって、逆順のデータに対してすべて Ω(n²) となる。クイックソートは、一度に要素を 63 個分移動させることが 許可されている ため、その下限を回避できる。32 回の実際の交換によって 2,016 個の転倒が解消されるのは、1回の交換あたり 63 個の転倒解消であり、ステップ5によれば、これはその距離における単一の交換が達成し得る最大値である。パネルは転倒数も、それが意味する下限も計算していない。

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

学習の道すじ

秒ではなく仕事量を数える

この次に recursion-tree

参考文献 (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

42Math チーム · 更新 2026-05-27

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

ほぼソート済み - 入力データの分布によって、アルゴリズム間の相対的な効率が変わる。
逆順 - バブルソートは2,016回の比較と2,016回の交換を行います。64個の要素を逆順にすると全2,016組のペアが一斉に反転するため、どの比較でも順序違いが見つかるのです。クイックソートは334回の比較と64回の交換で処理を終え、自身のn·log₂nの基準値である384を下回ります。逆順の配列を分割する際、中央の要素が常に正確な中央値となるからです。
重複の多いデータ - わずか八種類の値から選ばれた八十個の要素。クイックソートは、n·log₂nの基準値506に対して534回の比較を要します。三つのプリセットの中で、結果が自身の基準線を上回るのはこのケースだけです。ピボットと等しい要素が交換されてしまい、そこから何の利点も得られないからです。バブルソートは変わらず3,160回の比較を行いますが、交換は1,330回にとどまります。隣り合うペアの多くが、すでに順序通りだからです。