計数ソートの仕組み・コード・計算量をわかりやすく解説

計数ソートが解決する問題

要素のペアを比較するだけのソートは、最悪ケースで Ω(n log n) 回の比較が必要です。計数ソートは、比較をまったく行わず、キーそのものを配列のインデックスとして使うことで、この限界を回避します。0〜100 の試験の点数、年齢、0〜255 のバイト値、星の評価のように、キーが小さな整数なら、どんな比較ソートよりも高速です。

代償は、キーの範囲に比例するメモリです。範囲全体に散らばった少数の64ビット整数をソートしようとすると、現実的でないほど大きなカウント用の配列が必要になります。

考え方と具体例

値が 0〜8 の範囲（k = 9）にある [4, 2, 2, 8, 3, 3, 1] をソートします。

1. 各値を数える：count[v] は v が現れる回数です。
2. 累積和：各カウントを、その値以下の要素の個数に置き換えます。すると count[v] は、v が入る最後の位置の1つ先を指します。
3. 要素を配置する：入力を右から左へたどり、各値 v について count[v] を1減らして、その位置に v を書き込みます。右から左へたどることで、等しい値は元の順序を保ちます。

その結果、1 はインデックス 0 に、2 が2つはインデックス 1 と 2 に、3 が2つは 3 と 4 に、4 はインデックス 5 に、8 はインデックス 6 に入ります。結果は [1, 2, 2, 3, 3, 4, 8] です。

Pythonでの実装

この安定版は、0 から k - 1 までの整数キーで、任意のオブジェクトをソートできます。

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

普通の整数だけをソートし、安定性が不要なら、カウントから出力を再構築するもっと単純な版が使えます。この版は、最小値の分だけずらすことで負の数も扱えます。

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

時間計算量と空間計算量

k が O(n) のとき、計数ソートは線形時間です。k が n よりずっと大きい場合、たとえば 0〜10⁹ の範囲に1,000個の値がある場合は、カウント配列の処理が支配的になり、比較ソートか基数ソートのほうが適しています。

計数ソートと他のソートの比較

ここで k はキーの範囲のサイズ、d は桁数、b は基数ソートで使う基数です。累積和を使って右から左へ要素を配置する場合、計数ソートは安定です。カウントから再構築する単純な版は、普通の整数なら同じ結果になりますが、キーに付随する他のデータを運ぶことはできません。

派生と、よくある間違い

• 基数ソートは、桁ごとに安定な計数ソートを1回ずつ実行する方法で、この考え方を大きな整数や固定長の文字列に拡張したものです。
• バケットソートは、値を範囲ごとにバケットに振り分けて各バケットをソートします。値が一様に分布している場合に高速です。
• ソートしない数え上げ：ヒストグラムを作る、最頻値を求めるなど、必要なのがカウントだけの場面もよくあります。collections.Counter が直接それを行います。

計数ソートを使う場面

キーが、要素数に比べて小さな範囲の整数である場合に使います。成績、年齢、月の日付、バイト値、0〜255 の色チャンネルの値、小さな列挙型の値などです。基数ソートや接尾辞配列の構築アルゴリズムの内部ステップでもあります。面接では、色のソート（値は 0、1、2）、頻度によるソート、H-index といった問題や、比較ソートの O(n log n) の限界をどう超えるかという定番の質問で登場します。