計数ソート・基数ソート

計数ソート・基数ソート#

比較に基づくソートの下限は \(\Omega(n \log n)\) だが、計数ソートと基数ソートは比較を使わないことで \(O(n)\) を達成する非比較ソート。値の範囲に制約がある場合に有効。

計数ソート（Counting Sort）#

各値の出現回数を数え、累積カウントから各要素の最終位置を決定する。

計算量

時間計算量

\(O(n + k)\)（\(k\) は値の範囲）

空間計算量

\(O(n + k)\)

特徴

  • 安定ソート

  • 値が整数で範囲 \(k\) が小さい（\(k = O(n)\)）場合に有効

  • \(k \gg n\) のとき非効率（例：\(n=10\)、値域 \([0, 10^9]\)）

def counting_sort(arr: list[int], max_val: int | None = None) -> list[int]:
    """非負整数のリストをソート。max_val 省略時は自動検出"""
    if not arr:
        return []
    k = (max_val if max_val is not None else max(arr)) + 1

    # ステップ1: 出現回数をカウント
    count = [0] * k
    for x in arr:
        count[x] += 1

    # ステップ2: 累積カウント（各値の最終位置の右端）
    for i in range(1, k):
        count[i] += count[i - 1]

    # ステップ3: 後ろから配置（安定性を保つ）
    output = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        output[count[x]] = x

    return output

data = [4, 2, 2, 8, 3, 3, 1]
print("入力:", data)
print("出力:", counting_sort(data))

import random
random.seed(5)
large = [random.randint(0, 100) for _ in range(200)]
assert counting_sort(large) == sorted(large)
print("ランダム200件 (値域0-100): OK")

入力: [4, 2, 2, 8, 3, 3, 1]
出力: [1, 2, 2, 3, 3, 4, 8]
ランダム200件 (値域0-100): OK

基数ソート（Radix Sort）#

数値を桁ごとに安定ソートを繰り返す。最下位桁から順に処理する LSD（Least Significant Digit）が一般的。

計算量

時間計算量

\(O(d \cdot (n + b))\)（\(d\): 桁数、\(b\): 基数）

空間計算量

\(O(n + b)\)

特徴

  • 安定ソート

  • 値の範囲が広い整数（例：32bit）でも基数 \(b=256\)、桁数 \(d=4\) で効率的

  • 各桁の内部ソートに計数ソートを使う

def radix_sort(arr: list[int], base: int = 10) -> list[int]:
    """非負整数の LSD 基数ソート"""
    if not arr:
        return []
    a = arr.copy()
    max_val = max(a)
    exp = 1  # 現在処理中の桁の重み
    while max_val // exp > 0:
        a = _counting_sort_by_digit(a, exp, base)
        exp *= base
    return a

def _counting_sort_by_digit(arr: list[int], exp: int, base: int) -> list[int]:
    n = len(arr)
    output = [0] * n
    count = [0] * base

    for x in arr:
        digit = (x // exp) % base
        count[digit] += 1

    for i in range(1, base):
        count[i] += count[i - 1]

    for x in reversed(arr):
        digit = (x // exp) % base
        count[digit] -= 1
        output[count[digit]] = x

    return output

import random

data = [170, 45, 75, 90, 802, 24, 2, 66]
print("入力:", data)
print("出力:", radix_sort(data))

# 大きな値域でも有効
random.seed(6)
large = [random.randint(0, 10**9) for _ in range(500)]
assert radix_sort(large) == sorted(large)
print("ランダム500件 (値域0-10^9): OK")

# 基数 256 で 32bit 整数
large2 = [random.randint(0, 2**32 - 1) for _ in range(500)]
assert radix_sort(large2, base=256) == sorted(large2)
print("32bit整数 500件 (基数256): OK")

入力: [170, 45, 75, 90, 802, 24, 2, 66]
出力: [2, 24, 45, 66, 75, 90, 170, 802]
ランダム500件 (値域0-10^9): OK
32bit整数 500件 (基数256): OK

比較ソートとの計算量比較#

アルゴリズム

時間計算量

安定

in-place

制約

計数ソート

\(O(n+k)\)

✓

✗

整数、\(k=O(n)\)

基数ソート

\(O(d(n+b))\)

✓

✗

整数

バケットソート

\(O(n)\) 平均

✓

✗

一様分布

マージソート

\(O(n\log n)\)

✓

✗

なし

クイックソート

\(O(n\log n)\) 平均

✗

✓

なし

ヒープソート

\(O(n\log n)\)

✗

✓

なし
Contents