計数ソート・基数ソート - データサイエンス関連+αのメモ

比較に基づくソートの下限は $\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)$	✗	✓	なし