バケットソート — Project Hematite

カウントソートは各整数キーを直接インデックスにマッピングすることで線形時間を達成する。バケットソートはこのアイデアを一般化する：キー値ごとに 1 スロットの代わりに少数のバケットを確保し、それぞれが値の範囲をカバーし、小さなバケットを独立してソートする。値が範囲全体に一様に分布しているとき、各バケットは平均 $O(1)$ 個の要素を受け取り、すべてのバケットのソートの合計コストは $O(n)$ だ。

アルゴリズム

$[0, 1)$ に一様分布する $n$ 個の浮動小数点値が与えられたとする：

作成 — $k$ 個の空のバケットを作る。バケット $i$ は区間 $[\,i/k,\; (i+1)/k\,)$ をカバーする。
分配 — 各要素 $x$ をバケット $\lfloor x \cdot k \rfloor$ に入れる。
ソート — 各バケットを挿入ソートでソートする（バケットは平均して小さい）。
結合 — バケットを順番に結合する。

const std = @import("std");

fn insertionSortF64(arr: []f64) void {
    var i: usize = 1;
    while (i < arr.len) : (i += 1) {
        const key = arr[i];
        var j = i;
        while (j > 0 and arr[j - 1] > key) : (j -= 1) {
            arr[j] = arr[j - 1];
        }
        arr[j] = key;
    }
}

/// arr をインプレースでソートする。すべての値は [0, 1) 内でなければならない。
fn bucketSort(arr: []f64, allocator: std.mem.Allocator) !void {
    const k = arr.len;
    if (k == 0) return;

    // k 個のバケットを確保する。各バケットは拡張可能なリスト。
    const buckets = try allocator.alloc(std.ArrayList(f64), k);
    defer {
        for (buckets) |*b| b.deinit();
        allocator.free(buckets);
    }
    for (buckets) |*b| b.* = std.ArrayList(f64).init(allocator);

    // 要素をバケットに分配する。
    for (arr) |x| {
        const idx: usize = @intFromFloat(x * @as(f64, @floatFromInt(k)));
        try buckets[@min(idx, k - 1)].append(x);
    }

    // 各バケットをソートして書き戻す。
    var pos: usize = 0;
    for (buckets) |*b| {
        insertionSortF64(b.items);
        for (b.items) |x| {
            arr[pos] = x;
            pos += 1;
        }
    }
}

@min(idx, k - 1) のガードは浮動小数点の丸めにより x がちょうど 1.0 になるエッジケースを処理し、インデックスを最後の有効なバケットにクランプする。

なぜ $k = n$ バケットか？

$k = n$ とすることで一様分布のもと各バケットの期待負荷が 1 要素になる。以下の分析はこの選択を使うが、任意の固定 $k$ でも動作する — $k$ を小さくするとバケットが少なく（大きく）なり、メモリが限られている場合に好ましい。

平均ケースの分析

$n$ 個の入力値が $[0, 1)$ から独立一様に抽出されると仮定する。 $X_i$ をバケット $i$ の要素数とする。期待されるソートコストは：

E\!\left[\sum_{i=0}^{n-1} O(X_i^2)\right] = \sum_{i=0}^{n-1} O\!\left(E[X_i^2]\right).

各要素は確率 $1/n$ でバケット $i$ に入るので、 $X_i$ は $\text{Binomial}(n, 1/n)$ 分布に従う。この分布では：

E[X_i^2] = \operatorname{Var}(X_i) + (E[X_i])^2 = \frac{n-1}{n^2} + 1 \approx 2 - \frac{1}{n} = O(1).

$n$ 個すべてのバケットで合計すると：期待合計時間は $O(n)$ だ。

最悪ケースの挙動

一様分布の仮定が重要だ。 $n$ 個すべての要素が同じバケットに入ると、そのバケットは挿入ソートで $O(n^2)$ かかり、合計で $O(n^2)$ になる。バケットソートは値がバケット全体に広がっている場合のみ効率的だ。

他のキー型への拡張

$[0, 1)$ の範囲は慣習的だが必須ではない。任意の範囲 $[lo, hi)$ は正規化によって対応できる： $x \mapsto (x - lo) / (hi - lo)$ 。整数キーに対して各キー値に 1 要素のバケットソートはカウントソートに退化する — カウントソートは各バケットが最大 1 つの異なる値を持つバケットソートの特殊ケースだ。

計算量まとめ

指標	計算量
期待時間	$O(n)$ （一様入力、 $k = n$ ）
最悪ケース時間	$O(n^2)$
余分な空間	$O(n + k)$
安定	はい（バケット内の挿入ソートが順序を保つ）

余分な空間はバケット構造とバケットの内容をカバーする。 $k = n$ のとき $O(n)$ だ。

バケットソートを使う場面

入力が既知の範囲でほぼ一様に分布している。
$O(n)$ の余分なメモリを使える。
キー型がバケットインデックスへの高速なマッピングをサポートしている（浮動小数点の乗算、整数の除算）。

分布が偏っているとバケットソートは劣化する。整数キーで小さな範囲ならカウントソートを、汎用の比較ベースのニーズにはクイックソートやマージソートを使う。

まとめ

バケットソートはキー範囲によって要素を $k$ バケットに分配し、各バケットをソートして結合する。
$k = n$ バケットと一様分布入力で期待時間は $O(n)$ だ。
すべての要素が 1 バケットに集中すると最悪ケース時間は $O(n^2)$ になる。
空間は $O(n + k)$ ；安定性はバケットごとのソートアルゴリズムによる（挿入ソートは安定）。
カウントソートは各異なるキー値に 1 スロットを割り当てたバケットソートの特殊ケースだ。