クイックソート

つなぐときに、また比べ直している

マージソートは真ん中でまっぷたつに割ります。割った時点では、どちらの側にどんな値が入ったか分かりません。だから最後につなぐときに、あらためて全部を見比べる必要がありました。

では、割る前に基準を決めておけばどうでしょう。「この値より小さいものは左の箱、大きいものは右の箱」と振り分けてしまえば、左の箱の中身は右の箱のどれよりも小さいと確定します。つなぐときに比較は 1 回も要りません。

基準を 1 つ選んで、3 つの箱に配る

[6, 3, 8, 5, 2, 7, 1, 4] の真ん中の値 5 を基準にします。先頭から 1 つずつ見て、箱に入れていきます。

• 5 より小さい箱 — 3, 2, 1, 4
• 5 と等しい箱 — 5
• 5 より大きい箱 — 6, 8, 7

同じやり方で左の箱を並べると [1, 2, 3, 4]、右の箱は [6, 7, 8] になります。あとは順につなぐだけで [1, 2, 3, 4, 5, 6, 7, 8] です。基準の 5 は、配った時点ですでに最終的な位置が決まっていました。

等しい値の箱を別に作るのがコツです。基準そのものを小さい箱にも大きい箱にも入れないので、配るたびに要素が必ず 1 つ以上減ります。[3, 3, 3, 3] のように全部同じ値でも、1 回配れば等しい箱に全部入って終わります。

基準の選び方で速さが決まる

配るたびに中身が半分ずつになれば、段の数は要素数を 2 で割り続けられる回数で済みます。問題は、半分にならない選び方をしたときです。

nums = [1, 2, 3, 4, 5]
pivot = nums[0]   # 先頭を基準にすると
# 小さい箱は空、大きい箱は [2, 3, 4, 5]

1 個しか減っていません。これを繰り返すと段が要素数ぶん積み上がり、手間は 2 乗に戻ります。しかも、こうなるのは並べ替える必要がいちばん薄い「すでに並んだ入力」のときです。真ん中を取る、乱数で選ぶ、先頭と真ん中と末尾の 3 つの中央値を取る、といった選び方はこれを避けるための工夫です。

ここまでの 5 つを並べておきます。

よくある間違い

基準の値をどの箱にも入れ忘れることです。小さい箱と大きい箱の 2 つだけで振り分けると、基準そのものが結果から消えます。逆に、基準を大きい箱のほうにも残してしまうと要素が減らず、同じ配列をいつまでも配り続けます。

演習で使う書き方

本文の三つの箱への分配を、自分で関数にします。内包表記は使わず、for と if / elif / else、末尾に一要素を足す append を使います。配列の + は連結です。空の箱を用意したので、比較による分配と、停止条件と左右の再帰を書いてください。

1. 停止条件・基準との比較による分配・左右への再帰を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える