「ソートアルゴリズムで一番速いのは?」と聞かれたら、たいていクイックソートという答えが返ってくる。名前からしてそう言っている。

ただ、その評判には条件がついていたはずだ。どういう条件で、外れるとどうなるのか。

8種類のアルゴリズムを実装して、5種類の入力で回した。いちばん驚いたのは、教科書どおりに書いたクイックソートがバブルソートと1回も違わない比較回数を出した瞬間だった。

実験に使ったコードの全文はGitHubに置いています。

まず、動いているところを見る

48個の数を並べ替える様子を、4つのアルゴリズムで並べた。

1コマが比較1回に対応している。だから先に終わったパネルほど、比較の回数が少なかったということだ。クイックソートが261回で最初に終わり、選択ソートは1,128回かかっている。

以下、この「比較回数」を物差しにする。実行時間ではなく比較回数を数えるのには理由があって、Pythonの標準 sorted() だけがC言語で書かれているので、実行時間で比べるとアルゴリズムの差ではなく実装言語の差を見ることになってしまう。比較回数なら、どの言語で書いても同じ数字になる。

8種類 × 5種類の入力

2000個の数を並べ替えるのに何回比較したか、全部数えた。

赤いところが「たくさん比較した」、青いところが「少なくて済んだ」だ。

いちばん目を引くのがクイックソート(先頭ピボット)の行で、青と赤が入り混じっている。

入力	比較回数
ランダム	26,419
ソート済み	1,999,000
逆順	1,999,000
ほぼ整列済み	658,602
重複だらけ	206,154

ランダムから並べ替え済みに変えるだけで、76倍になっている。

そして1,999,000という数字は、同じ表のバブルソートと選択ソートの数字と1回も違わない。$2000 \times 1999 \div 2 = 1{,}999{,}000$。総当たりで全部のペアを比べたのと同じ回数だ。

なぜ「並べ替え済み」が最悪なのか

クイックソートの仕組みを簡単に。

1. 配列から1個選ぶ(これをピボットと呼ぶ)
2. 残りを「ピボットより小さい組」と「大きい組」に振り分ける
3. それぞれの組を、同じやり方で並べ替える

うまくいくと、2の振り分けで配列が半分ずつに割れる。半分の半分の半分…と進むので、10回も割れば1000個が1個になる。これが速さの理由だ。

問題は、ピボットに何を選ぶかにある。教科書のいちばん短いコードは「先頭の要素」を選ぶ。

ここで並べ替え済みの配列を渡すと、先頭は最小値だ。「これより小さい組」は空っぽ、「大きい組」は残り全部。半分に割れず、1個ずつしか減らない。

$1999 + 1998 + 1997 + \cdots + 1 = \frac{2000 \times 1999}{2} = 1{,}999{,}000$

きれいに総当たりの回数になる。分割統治のつもりが、1個ずつ確認しているだけになっていた。

nを変えて確かめた。

n	ソート済みを入れたとき	$n(n-1)/2$
100	4,950	4,950
400	79,800	79,800
1,600	1,279,200	1,279,200

ぴたりと一致した。 1回の誤差もない。

この「並べ替え済みが最悪」というのが厄介なのは、現実のデータでいちばんありふれた形だからだ。日付順に並んだログ、IDの昇順で取ってきたレコード、前回ソートした結果。ランダムなデータのほうが、実務ではむしろ珍しい。

直し方は1行

対策は昔から知られていて、ピボットをランダムに選ぶだけでいい。

k = random.randrange(len(a))
a[0], a[k] = a[k], a[0]   # これを足すだけ
pivot = a[0]

同じ表の「クイックソート(乱択ピボット)」の行を見ると、ランダム24,778、ソート済み24,633、逆順24,898、ほぼ整列済み25,326。入力の種類が変わってもほとんど動かない。

先頭を選ぶと1,999,000、ランダムに選ぶと24,633。1行で81倍だ。

それでも残る弱点:同じ値だらけの入力

乱択ピボットの行に、1つだけ赤いマスが残っている。重複だらけ(値が10種類しかない)で205,414回。他の列の8倍だ。

理由は、振り分けが「ピボットより小さい」と「そうでない」の2つしかないこと。値が10種類しかないと、ピボットと等しい要素が大量に「そうでない」側に流れ込む。何度分割してもその塊が減らない。

対処は3つに分ける方法(3-way partition)で、「小さい」「等しい」「大きい」に振り分ける。等しい組はもう並べ替える必要がないので、そこで終わりにできる。

重複だらけ(2000個、値は10種類)	比較回数
クイックソート(乱択ピボット)	205,414
クイックソート(3分割)	10,370

20倍の差がついた。カテゴリ、都道府県、ステータス——値の種類が少ない列は実務にいくらでもある。

ここで、前提が崩れる

さて、ここまで書いておいて何だが、この記事の物差しでは「クイックソートが最速」は成り立たなかった。

ランダムな2000個で比較回数がいちばん少なかったのは、クイックソートではない。

アルゴリズム	ランダム2000個の比較回数
マージソート	19,390
クイックソート(乱択ピボット)	24,778
クイックソート(先頭ピボット)	26,419
ヒープソート	37,739
挿入ソート	1,001,827
選択ソート	1,999,000

マージソートが1位で、クイックソートは2位だ。しかもマージソートは、どの入力でも11,000〜19,000の範囲に収まっていていちばん安定している。

では「クイックソートが最速」は嘘なのか。そうではなくて、測っている量が違う。

クイックソートの強みは比較の少なさではない。

• 追加のメモリがいらない。マージソートは作業用に元と同じ大きさの配列を要求する
• メモリへのアクセスが連続している。配列を前から順に触るのでCPUのキャッシュに乗りやすく、1回あたりの比較が物理的に速い

比較回数では負けていても、実行時間では勝つ。この記事の物差しは前者しか見ていない。

「小さい配列では挿入ソートのほうが速い」という定番の話も、同じ理由で比較回数には現れなかった。

n=8の時点でもうマージソートが勝っていて、逆転する点がない。挿入ソートが小さい配列で速いのは、比較が少ないからではなく1回あたりの処理が単純で軽いからだ。だから実際のライブラリは、分割が小さくなったところで挿入ソートに切り替える。

何を測るかで順位が変わる。 これはアルゴリズムの話であると同時に、実験の設計の話でもあった。

Pythonの sorted() は何をしているのか

最後に、実務で実際に使うものを測った。Pythonの sorted() はTimsortという方式で、マージソートと挿入ソートを組み合わせたものだ。

20万個を並べ替えるのにかかった時間。

入力	時間
ランダム	40.2 ms
ソート済み	4.3 ms
逆順	4.0 ms
ほぼ整列済み	6.9 ms
重複だらけ	12.9 ms

並べ替え済みだと9.4倍速い。 Timsortは「すでに並んでいる区間」を先に探して、そこはそのまま使う。実データにはそういう区間が多いという観察から作られた方式で、ここまで見てきたクイックソートの弱点(並べ替え済みが最悪)とちょうど逆になっている。

逆順が4.0msなのも同じ理屈で、降順に並んだ区間を見つけたらひっくり返すだけで済ませている。

まとめ

• 先頭をピボットにしたクイックソートは、並べ替え済みの入力で比較回数が76倍(26,419 → 1,999,000)になる。この数字はバブルソートと完全に同じで、$n(n-1)/2$ に1回の誤差もなく一致した
• 原因は、先頭が最小値なので分割が「空っぽ」と「残り全部」になること。分割統治が機能していない
• ピボットをランダムに選ぶ1行で、入力の種類によらず24,000回台に収まる
• 乱択でも同じ値だらけの入力には弱い(205,414回)。3分割方式なら10,370回で20倍速い
• 比較回数で測ると1位はマージソート(19,390)でクイックソートは2位。クイックソートの強みは比較の少なさではなく、追加メモリ不要とメモリアクセスの連続性にある
• 「小さい配列では挿入ソートが速い」も比較回数には現れない。速いのは1回あたりの処理が軽いから
• Pythonの sorted() は並べ替え済みで9.4倍速い(40.2ms → 4.3ms)。すでに並んでいる区間を再利用している

実務で何を使うか

• 基本は言語の標準ソートを使う。 Timsortは実データの偏りを利用する設計になっていて、自分で書いたものが勝つことはまずない
• 自分で書くなら、ピボットは必ずランダムか中央値にする。先頭固定は現実のデータで踏み抜く
• 値の種類が少ない列を並べ替えるなら3分割を検討する
• 入力の「ありそうな形」で必ずテストする。 ランダムなテストデータだけで通すと、最悪ケースは本番まで出てこない

---

最悪ケースは、変なデータではなかった。きれいに並んだ入力だった。

普通、壊れるのは変な入力を渡したときだと思っている。だから極端な値や空の配列は試す。ところがここで壊れたのは、いちばん行儀のいい入力だった。もう並んでいる配列という、こちらが何も心配しなくていいはずのものが、最悪の性能を引き出す。

しかも壊れ方が静かだ。結果は正しく並んでいる。ログにも何も出ない。ただ76倍遅い。データが1万件に増えたとき、遅くなった理由をここに探しに来る人はまずいないと思う。

テストデータをランダムに作る癖が自分にはある。それは「偏りのない公平な試験」のつもりだったが、実際には現実に来る入力から一番遠い形を選んでいたのかもしれない。本番のデータは、日付順に並んでいるし、同じ値が繰り返し出てくるし、前回の処理結果が残っている。ランダムであることのほうが例外だった。

公平な試験と、意味のある試験は違う。試験の設計が現実から離れていると、通ってしまうこと自体が問題になる。

• 実践記
• アルゴリズム

関連記事

• ウラムの螺旋の斜めの線は本物だった。長い対角線の素数率39.28%に対し、ランダム対照200回の最大は15.46%
• 宝くじ仮説の枝刈りをnumpyで自前実装したら、当たりくじの優位はスパース率98%から先だけだった(99%で62%対48%)
• 主成分分析で「累積寄与率80%まで残す」を実測したら、捨てた寄与率1.88%の成分だけで精度0.95が出た

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。