並べ替え（ソート）のしかたを見る

バブルソートとクイックソートに同じ棒を同時に流して、競争させます。 比べた回数と入れかえた回数をその場で数えるので、速さの差がどこから来ているのかが見えます。

速さの差は「比べた回数」と「入れかえた回数」でできています

コンピュータが数を並べ替えるとき、やっていることはたった2つしかありません。2つを比べることと、2つを入れかえることです。 どんなに難しそうな名前のやり方でも、中身はこの2つのくり返しです。

ということは、速いやり方とは「この2つを少ない回数で済ませるやり方」のことになります。だからこのページは、動きを見せるだけでなくその場で回数を数えて出します。 上の図で2つのやり方が同時に走るのを見ると、 速いほうが先に止まって、遅いほうがまだ働き続けているのが分かります。その差が、そのまま回数の差です。

ここで数えている「手」は比べた回数と入れかえた回数を足しただけのものです。 本物のコンピュータでは、比べる1回と入れかえる1回にかかる時間は同じではありませんし、 数がどこに置かれているか（キャッシュ）でも変わります。時間そのものではなく、働いた量の目安だと思ってください。

ほぼ並んでいるデータでは、遅いはずのバブルソートが勝ちます

ここがこのページでいちばん見てほしいところです。上の「はじめの並び方」をほぼ整列済みにして走らせてみてください。教科書で「遅い」と言われるバブルソートが、先にゴールします。

からくりはこうです。バブルソートには「1回りして1度も入れかえなかったら、そこでやめる」という決まりがあります。 ほとんど並んでいるデータなら、2回りもすれば入れかえるところが無くなるので、そこで気づいて止まれるのです。12本で2組だけ入れちがっている並びなら、 比べるのは21回、入れかえるのは2回で終わります。

いっぽうクイックソートは、データがもう並んでいるかどうかを気にしません。 毎回きちんと基準を決めて、全部を2つに分けていきます。ていねいな仕事が、ここでは裏目に出るわけです。

「逆転」の数を見ると、どれくらい散らかっているか分かります

逆転とは「左のほうが大きい組」のことです。 1・3・2 という並びなら、（3, 2）の1組だけが逆転です。すでに並んでいれば0組、 逆順ならいちばん多くなります。

面白いのはここからです。バブルソートの入れかえ回数は、この逆転の数とぴったり同じになります。となりどうしを入れかえると逆転がちょうど1つ消えるので、1回も余分に働けないし、1回も手を抜けないのです。 上の画面には逆転の数も出しているので、走らせる前に入れかえ回数を言い当てることができます。

クイックソートは「いつも速い」わけではありません

クイックソートは、まず基準（ピボット）をひとつ決めて、 それより小さい組と大きい組に分けます。速さはこの基準の選び方でまるごと変わります。 上の画面で基準を「いちばん右」に切り替え、並びを逆順にして走らせてみてください。

逆順のデータでいちばん右を基準にすると、毎回いちばん小さい値が基準になってしまい、分けても片方は空っぽです。 つまり1回分けても、1本しか場所が決まりません。 このとき比べる回数は、10本なら45回 ── これはバブルソートとまったく同じ45回です。偶然ではなく、 どちらも「全部の組み合わせを1回ずつ比べる」ことになるからで、 n本なら n × (n − 1) ÷ 2 回で一致します。

では基準をうまく選べば安全かというと、そうとも言い切れません。ダグ・マキルロイの論文「A Killer Adversary for Quicksort」（1999年）（新しいタブで開きます）は、比べられた順番を見ながら意地悪なデータを作っていく相手を用意すれば、 どんなクイックソートでも遅くできることを示しました。 論文の要旨には「この一般的な方法は、ごくゆるやかで現実的な条件を満たすどんなクイックソートに対しても効く ── 乱数を使うものに対してさえ」 と書かれています。

だからこのページでは「クイックソートが常に速い」とは書きません。 速いやり方には速い理由があり、遅くなる条件もいっしょに付いてきます。条件を知らずに名前だけ覚えるのは、道具の名前だけ覚えて使い方を知らないのと同じです。

クイックソートは、ロシア語の単語を辞書で引くために生まれました

クイックソートを考えたのは、イギリスのトニー・ホーア（C. A. R. Hoare）という人です。生まれたのは1959年、場所はモスクワでした。

オックスフォード大学のホーア本人の紹介文には、「1959年、モスクワ国立大学の大学院生として機械翻訳を研究していた。 辞書で単語を効率よく引くために、彼はよく知られた並べ替えの方法であるクイックソートを見つけた」（新しいタブで開きます）と書かれています。

つまりもとの目的は翻訳でした。ロシア語の文を英語に直すには、 文に出てくる単語を辞書で引かなければなりません。当時の辞書は磁気テープの上にアルファベット順に並んでいたので、 調べたい単語のほうも先にアルファベット順に並べておかないと、 テープを何度も巻き戻すことになります。並べ替えは目的ではなく、目的のための下ごしらえだったわけです。

手順が論文として世に出たのは2年後、Communications of the ACM 誌の「Algorithm 64: Quicksort」（1961年・第4巻7号321ページ）（新しいタブで開きます）です。たった1ページの短い文章ですが、いまも世界中のコンピュータの中で動いています。

本物のコンピュータは「ほぼ並んでいる」を見つけて利用しています

「ほぼ並んでいるデータは速く並べられる」という話は、教室の中だけの話ではありません。 現実のデータは、たいてい完全にバラバラではないからです。 日付順に記録されたものを金額順に並べ直すときなど、途中まで並んでいる部分があちこちに残っています。

プログラミング言語 Python が並べ替えに使っているTimsortは、まさにそこを狙って作られました。Python の設計メモ（listsort.txt）（新しいタブで開きます）の1行目には「これは適応的で、安定で、自然なマージソートについて書いたものだ」 とあります。適応的というのは 「データがどれくらい並んでいるかを見て、やり方を変える」という意味です。

Timsort はまずすでに並んでいる部分（ラン）を探し、 それをつなぎ合わせていきます。だから完全にバラバラなデータより、 途中まで並んだデータのほうがずっと速く終わります。バブルソートが「もう並んでいる」と気づいて止まるのと、考え方は同じです。 小さな工夫に見えるものが、そのまま本物の道具の設計思想になっています。

これ以上は速くできない、という下限があります

新しいやり方をどれだけ工夫しても、ここから先は速くできないという壁があります。 数えかたはこうです。

n本の棒の並び方はn!（nの階乗）通りあります。8本なら40,320通り、 12本なら4億7900万通りです。いっぽう1回くらべて分かることは、 「はい」か「いいえ」の2通りだけ。ということは、k回くらべて見分けられるのは 多くても2のk乗通りしかありません。

2のk乗が n! 以上でなければ、どの並びだったのか決められません。だから、くらべることだけで並べ替えるやり方は、いちばん悪い場合に少なくとも log2(n!) を切り上げた回数だけくらべることになります。 8本なら16回、12本なら29回、20本なら62回です。

これは「いちばん悪い場合」の話で、 1回1回の並べ替えが必ずこの回数かかるという意味ではありません。 すでに並んでいる8本なら、バブルソートは7回くらべただけで終わります。当たりを引いたときに速いことと、どんな並びが来ても大丈夫なことは別です。 なお、この下限は「くらべて決める」やり方に限った話で、 値そのものを住所として使うやり方（バケツソートなど）は、この壁の外側にあります。

貼ったものも、並べたものも、どこにも送っていません

この画面の並べ替えは、すべてあなたの端末の中で計算しています。 棒の並びをサーバーへ送ってもいませんし、保存もしていません。 ページを読み込み直すと、はじめの並びに戻ります。

「かきまぜる」を押したときだけ、端末の暗号用の乱数 （crypto.getRandomValues）を使っています。 そのままあまりを取るとかたよりが出るので、割り切れない分は捨てて引き直しています ── かたよりの話はサイコロを振るのページに書きました。 それ以外の場面では乱数を1回も使っていません。 全ページを先に作っておく作りなので、画面を描いている途中で乱数を引くと、最初の一瞬だけ別の並びが出てしまうからです。