ソートアルゴリズム対決

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