カウントソート
比べている限り、これ以上は速くならない
ここまでの 5 つは、どれも「2 つの値を比べる」ことを土台にしていました。比較だけで並べ替える限り、手間は O(n log n) より下には行けません。これは工夫が足りないからではなく、比較 1 回で得られる情報が「どちらが大きいか」の 2 択しかない、という上限から来ています。
では、比べるのをやめてみます。
数え終わった時点で、並び順はもう決まっている
5 段階のアンケート [3, 1, 4, 1, 5] を並べたいとします。1 から 5 までのマスを用意して、出てきた数だけ印をつけます。
Python
votes = [3, 1, 4, 1, 5]
box = [0] * 6 # 0 から 5 までのマス
for v in votes:
box[v] += 1
print(box) # [0, 2, 0, 1, 1, 1]box[1] が 2、box[3] が 1、box[4] が 1、box[5] が 1。ここから左のマスから順に「1 を 2 個、3 を 1 個、4 を 1 個、5 を 1 個」と書き出せば [1, 1, 3, 4, 5] です。値を一度も比べていません。
速い理由は、マスの番号がそのまま順番になっていることです。並べる作業を、数える作業に置き換えています。入力を 1 回なめ、マスを 1 回なめるだけなので、手間は要素数と値の幅の合計で決まります。掛け算ではなく足し算なのがここでの勝ち筋です。
100 万件のアンケート結果を並べる場合で比べてみます。比較する並べ替えなら、要素数に段数を掛けて 2,000 万回ほど。数えるほうは、100 万回なめてマス 5 個を見るだけです。差は 20 倍近くになります。
負の数が来ると、マスの番号が足りない
[-2, 0, -5, 3] を同じやり方で扱おうとすると困ります。マスの番号は 0 から始まるのに、値が -5 だからです。
考え方は、いちばん小さい値を 0 番のマスに対応させることです。値そのものではなく、最小値からいくつ離れているかでマスを決めます。書き出すときは逆に、マスの番号から最小値ぶん戻せば元の値に復元できます。マスの数は、最大値と最小値の差に 1 を足したぶんだけ要ります。
もう 1 つ、この方法が向かない場面があります。[1, 1000000000] のように値の幅が広いと、2 個を並べるために 10 億個のマスを確保しようとして落ちます。要素数に比べて値の幅が広すぎるときは、比較する並べ替えのほうが速いです。
よくある間違い
空の配列を渡されたときに、最小値を求めようとして落ちることです。マスの大きさは最小値と最大値から決めるので、要素が 1 つも無いと計算のしようがありません。数え始める前に、空かどうかだけ確かめておいてください。
演習で使う書き方
例として値 [4, 6, 4] なら、最小値 4 を 0 番に合わせ、箱の個数は [2, 0, 1] です。0 番の値を二回、2 番の値を一回出せば [4, 4, 6]。[0] * 長さ は空の箱の確保、append は一要素の追加です。対応づけ・集計・復元を書きます。
要件
- 値と箱の対応・個数の集計・順に復元を自分で実装する
- 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える