カウントソート
比べている限り、これ以上は速くならない
ここまでの 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 つも無いと計算のしようがありません。数え始める前に、空かどうかだけ確かめておいてください。
要件
- 比較ベースのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
- 値の出現回数を数えるカウントソートで実装する
- 負の数を含む入力でも動作するように、min / max のオフセットを使う
入出力例
countingSort([3,1,4,1,5,9,2,6,5,3]) → [1,1,2,3,3,4,5,5,6,9]
countingSort([1,2,3]) → [1,2,3]
countingSort([5,4,3,2,1]) → [1,2,3,4,5]
countingSort([7,7,7]) → [7,7,7]
countingSort([42]) → [42]
countingSort([-2,0,-5,3,0]) → [-5,-2,0,0,3]ヒント
