バケットソート入門：原理・計算量・実装例（Python）と並列化のポイント
エバープレイ編集部バケットソートとは
バケットソート（Bucket Sort）は、入力データを複数の「バケット（桶）」に分割してから、各バケット内を個別にソートして全体を整列する比較ベース外のソート手法の一つです。特に値が一様に分布している場合に高い性能を発揮し、適切にバケット数と分配関数を選べば平均的に線形時間に近い性能が得られます。数値データのソートでよく使われ、安定化や並列化もしやすい特徴があります。
基本アイデア
- 入力の値域（または正規化された範囲）をいくつかの区間（バケット）に分ける。
- 各要素を対応するバケットに割り当てる（ハッシュ的な分配）。
- 各バケット内の要素を別のソート法（挿入ソートやクイックソートなど）でソートする。
- バケットを順に連結して最終的なソート列を作る。
例えば、[0,1) に値が一様に分布する実数列をソートする場合、B 個のバケットを用意して要素 x を floor(B * x) のバケットに入れるだけで、各バケットの期待サイズは n/B になります。B を n に近づければ各バケットの期待サイズは定数となり、バケット内部のソートが定数時間で済むため全体が O(n) の期待時間で動作します。
アルゴリズムの手順（典型）
- バケット数 B を決める（経験的に n や n/10、sqrt(n) など）。
- 空のバケット配列 buckets[0..B-1] を作る（リストや可変配列）。
- 各入力 x を正規化して適切なバケット index = bucket_index(x) に push する。
- 各 buckets[i] を安定ソート（例：挿入ソート）でソートする。
- バケットを順に連結して結果を出力する。
計算量と安定性
- 期待時間（平均的な場合）: よく分布していると仮定すると O(n + B + sum_i T(bucket_i))。通常 B を O(n) にとれば期待 O(n)。
- 最悪時間: 全要素が同一バケットに集中するとバケット内のソートに依存し、たとえば挿入ソートを用いれば O(n^2) になる。
- 空間計算量: 追加のバケット領域が必要。総メモリは O(n + B)（バケット配列＋バケット内の格納領域）。
- 安定性: バケット割付自体は安定にできる（入力の到着順を保持してバケットに append する）。ただし、バケット内部で用いるソートアルゴリズムが安定であることが必要で、そうすれば全体として安定ソートとなる。
期待時間の詳細解析（簡易）
n 要素を B 個のバケットに均等に分配すると各バケットの期待サイズは n/B。もし各バケットを挿入ソート（O(k^2)）でソートするなら、総コストの期待値は O(n) + sum E[O(n_i^2)]。均等分布なら sum E[n_i^2] = B * (n/B)^2 = n^2 / B。したがって総期待コストは O(n + n^2 / B)。ここから B を O(n) に設定すれば期待 O(n) が得られます。
実装上の工夫と注意点
- 分配関数（バケット割当関数）は重要。データが既知の分布に沿うならそれに合わせてスケーリングを行う。例：最小値と最大値を使って正規化する。
- 非一様分布の場合、特定バケットに偏ると性能が落ちる。動的にバケットの数を増やす、再分配（リバケット化）を行う、またはバケット内で効率的なソート（クイックソートやヒープソート）を使うことで最悪時の影響を抑える。
- 整数キーや有限レンジのデータには計数ソート（Counting Sort）や基数ソート（Radix Sort）がより適している場合がある。計数ソートはキーの範囲が小さいときに特に高速。
- 浮動小数点や実数では値を範囲に正規化して bucket_index = floor((x - min) / (max - min) * B) のように割り当てる。
- バケット内部のデータ構造は可変長配列か連結リスト。多くの環境では可変配列（ベクタ）を使う方がメモリ局所性が良く高速。
実装例（Python 風 疑似コード）
def bucket_sort(array, B):
if len(array) == 0: return array
min_v, max_v = min(array), max(array)
if min_v == max_v: return array
# バケットの初期化
buckets = [[] for _ in range(B)]
for x in array:
# 正規化してバケット決定
idx = int((x - min_v) / (max_v - min_v) * (B - 1))
buckets[idx].append(x)
# 各バケットをソートして連結（ここでは安定なソートを仮定）
result = []
for b in buckets:
b.sort() # 小さいバケットなら挿入ソートでも良い
result.extend(b)
return result
他のソートとの比較
- 計数ソート（Counting Sort）: キーが小さい整数に適し、O(n + k) 時間。バケットソートと違い、個々のキーの出現数を数える方法。
- 基数ソート（Radix Sort）: 固定長のキー（整数や文字列）を桁ごとにソートする手法で、計数ソートを内部に使うことが多い。安定で線形に近い性能。
- 比較ベースのソート（クイックソート、マージソート）: 一般的で最悪 O(n log n)（クイックは期待 O(n log n)、マージは安定で O(n log n)）だが、データ分布に依らず安定した性能を示す。
実用例と用途
- 実数の大量ソートで値域が既知か正規化可能で、かつ値が一様に近い場合。
- 並列・分散処理との相性が良い：バケットごとに独立してソート作業を割り当てられるため、MapReduce スタイルの分散ソートやマルチスレッド実装で有効。
- 安定性が必要なソートや、データがヒストグラム的に偏っていないログや計測値のソート。
並列化と分散実装
バケットへの振り分けはデータ独立な操作であり、各バケットを別スレッド／プロセスでソートすることで大きくスピードアップできます。分散環境では、キーのレンジ分割をマッピング関数として使い、各ノードに範囲を割り当ててローカルでソート、最後にマージする手法（レンジパーティショニング）がバケットソートの考え方に近い実装例です。
まとめ
バケットソートは「分配（bucket）」＋「局所ソート」というシンプルなアイデアに基づくアルゴリズムで、データの分布を活かせれば平均的に非常に高速（ほぼ線形）になります。ただし分布が偏ると最悪二乗時間になるなどリスクもあるため、用途やデータ特性、バケット数の選定、バケット内ソート法の選択が重要です。並列化が容易で、実装次第で安定性も確保できるため、用途に合えば非常に有効な手法です。
