バケットソート¶
前述のいくつかのソートアルゴリズムは、いずれも「比較ベースのソートアルゴリズム」に属し、要素間の大小を比較することで整列を実現します。この種のソートアルゴリズムの時間計算量は \(O(n \log n)\) を超えられません。続いて、時間計算量が線形オーダーに達しうる「非比較ソートアルゴリズム」をいくつか見ていきます。
バケットソート（bucket sort）は分割統治戦略の典型的な応用です。大小関係をもつ複数のバケットを用意し、各バケットがあるデータ範囲に対応するようにして、データを各バケットへ均等に分配します。その後、各バケット内でそれぞれソートを行い、最後にバケットの順序に従ってすべてのデータを結合します。
アルゴリズムの流れ¶
長さ \(n\) の配列を考え、その要素は範囲 \([0, 1)\) の浮動小数点数であるとします。バケットソートの流れを以下の図に示します。
- \(k\) 個のバケットを初期化し、\(n\) 個の要素を \(k\) 個のバケットに分配します。
- 各バケットに対してそれぞれソートを実行します（ここではプログラミング言語の組み込みソート関数を用います）。
- バケットを小さい順にたどって結果を結合します。
コードは以下のとおりです：
アルゴリズムの特性¶
バケットソートは、非常に大規模なデータの処理に適しています。たとえば、入力データに 100 万個の要素が含まれ、空間の制約によりシステムメモリへすべてのデータを一度に読み込めない場合です。このとき、データを 1000 個のバケットに分け、それぞれのバケットを個別にソートしてから、最後に結果を結合できます。
- 時間計算量は \(O(n + k)\) ：要素が各バケット内に平均的に分布していると仮定すると、各バケット内の要素数は \(\frac{n}{k}\) です。1 つのバケットをソートするのに \(O(\frac{n}{k} \log\frac{n}{k})\) の時間がかかるなら、すべてのバケットのソートには \(O(n \log\frac{n}{k})\) の時間がかかります。バケット数 \(k\) が十分大きいとき、時間計算量は \(O(n)\) に近づきます。結果を結合する際には、すべてのバケットと要素を走査する必要があり、\(O(n + k)\) の時間を要します。最悪の場合、すべてのデータが 1 つのバケットに割り当てられ、そのバケットのソートに \(O(n^2)\) の時間がかかります。
- 空間計算量は \(O(n + k)\)、非インプレースソート：\(k\) 個のバケットと合計 \(n\) 個の要素ぶんの追加領域が必要です。
- バケットソートが安定かどうかは、バケット内要素のソートに用いるアルゴリズムが安定かどうかに依存します。
均等な分配を実現するには¶
バケットソートの時間計算量は理論上 \(O(n)\) に達しますが、鍵は要素を各バケットへ均等に分配すること にあります。実際のデータは均一に分布していないことが多いからです。たとえば、Taobao 上のすべての商品を価格帯ごとに 10 個のバケットへ均等に分けたいとしても、商品の価格分布は偏っており、100 元未満は非常に多く、1000 元超は非常に少ないかもしれません。価格区間を単純に 10 等分すると、各バケットの商品数には大きな差が生じます。
均等な分配を実現するために、まず大まかな境界線を設定し、データをひとまず 3 個のバケットに粗く振り分けます。分配後は、商品数の多いバケットをさらに 3 個のバケットに分割し、すべてのバケット内の要素数がおおむね等しくなるまでこれを続けます。
以下の図に示すように、この方法の本質は再帰木を構築することにあり、目標は葉ノードの値をできるだけ均等にすることです。もちろん、毎回データを 3 個のバケットに分割する必要はなく、具体的な分け方はデータの特徴に応じて柔軟に選べます。
商品価格の確率分布をあらかじめ把握しているなら、データの確率分布に基づいて各バケットの価格境界を設定できます。なお、データ分布は必ずしも特別に統計を取る必要はなく、データの特徴に応じて何らかの確率モデルで近似することもできます。
以下の図に示すように、商品価格が正規分布に従うと仮定すれば、価格区間を合理的に設定でき、それによって商品を各バケットへ均等に分配できます。
