TUTORIAL · Algorithm

バケットソート

このチュートリアルでは、バケットソートアルゴリズムを紹介します。

このページの内容
注意
挿入ソートに馴染みがない場合は、先に挿入ソートの記事をお読みください。

バケットソートは比較ソートではなく、値の分布を利用するソートアルゴリズムです。値を順序に沿ったバケットに振り分け、各バケット内の値を並べ替えた後、バケットを順に連結して結果を得ます。既知の範囲に値が比較的均等に分布している場合に特に効果を発揮します。値をバケットに対応付ける適切な方法があるとき、この分配と収集の方法が役立ちます。

バケットソートのアルゴリズム

入力範囲を覆う k 個のバケットを用意し、各値をその値が属する区間のバケットに対応付けます。[0, 1) の値には、ゼロ始まりの簡潔な規則として floor(k * x) を使えます。このときバケット j が受け持つ区間は [j/k, (j+1)/k) です。上限は含まれないため、対象範囲内の値はすべて 0 から k - 1 までのインデックスに対応します。この範囲外の値には正規化か別の対応付けが必要です。この式がどの範囲にも使えるわけではありません。

手順は次のとおりです。

  1. 選んだ範囲を分割する k 個のバケットを作ります。
  2. 入力値 x を順に調べ、floor(k * x) 番目のバケットに入れます。
  3. 各バケットを個別に並べ替えます。小さなバケットには挿入ソートがよく使われますが、ほかの局所的なソート方法も利用できます。
  4. バケットをインデックス順にたどり、並べ替え済みの値を結果に追加します。

バケットへの対応付けによって、バケット間の順序は保たれます。バケット j のすべての値は、バケット j + 1 のどの値よりも小さくなります。同じ区間に入った値の順序は、各バケット内の並べ替えで整えます。上でリンクした挿入ソートの記事では簡単な局所ソートの方法を説明していますが、以下の実装では代わりに C++ 標準ライブラリの sort 関数を使います。

バケットソートの例

[0, 1) を10個の等しい区間に分けるため、インデックスには floor(10 * x) を使います。区間は [0.0, 0.1)、[0.1, 0.2) のように続き、最後は [0.9, 1.0) です。たとえば 0.1 は区間の左端を含むため、バケット1に入ります。

入力 (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31) を振り分けると、次のようになります。

バケット 区間 バケット内の並べ替え前の値
0 [0.0, 0.1) —
1 [0.1, 0.2) 0.1
2 [0.2, 0.3) 0.22, 0.21
3 [0.3, 0.4) 0.33, 0.38, 0.31
4 [0.4, 0.5) 0.45
5 [0.5, 0.6) 0.55
6–9 [0.6, 1.0) —

各バケットを並べ替えると、バケット2には 0.21, 0.22 が入り、バケット3には 0.31, 0.33, 0.38 が入ります。ほかの空でないバケットには、それぞれ値が1つだけ入っています。バケット0から9まで順に連結すると、昇順の (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55) が得られます。

バケットソートアルゴリズムの実装

この C++ プログラムでは、上の例と同じ8個の値を使います。値を10個のバケットに振り分け、各バケットを並べ替えてから、集めた値を出力します。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<double> bucketSort(const std::vector<double>& values,
                               std::size_t bucketCount) {
    std::vector<std::vector<double>> buckets(bucketCount);

    for (double value : values) {
        const std::size_t index = static_cast<std::size_t>(value * bucketCount);
        buckets[index].push_back(value);
    }

    std::vector<double> result;
    result.reserve(values.size());
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }
    return result;
}

int main() {
    const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
                                        0.38, 0.55, 0.21, 0.31};
    const std::vector<double> sorted = bucketSort(values, 10);

    std::cout << "Sorted values:";
    for (double value : sorted) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}
Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55

この関数は、bucketCount が正であり、すべての値が [0, 1) に含まれることを前提としています。この条件により、計算したインデックスがバケット用ベクターの範囲内に収まります。別の範囲を扱う場合は、インデックスを計算する前に値を正規化するか、その範囲に適した対応付けを定義してください。提示された実行結果では、このプログラムは正常に実行され、終了コードは0で、上に示したソート済みの列が得られています。出力ブロックに表示されるラベルは英語の Sorted values: です。

バケットソートアルゴリズムの計算量

値の個数を n、バケット数を k、バケット j に入る値の個数を b_j とします。バケットの作成と値の振り分けには O(n + k) 時間がかかります。各バケットで std::sort のような比較ソートを使う場合、追加の処理量は各バケットのソートコストの合計 O(Σ b_j log b_j) で抑えられます。そのため、1つのバケットに値が集中すると、合計時間は O(n log n) になることがあります。一般的には k を n に比例させ、入力がほぼ一様に分布していて各バケットが小さく保たれる場合、期待時間はほぼ線形になり得ます。アルゴリズムの名前だけでその性能が保証されるわけではありません。

バケット内で挿入ソートを使う場合、サイズ b_j のバケットは最悪で O(b_j²) 時間かかることがあります。値が1つのバケットに集中すると、全体の時間計算量が二次になる可能性があります。性能を見積もる際には、入力の分布とバケット内で使うソート方法の両方が重要です。

補助空間は O(n + k) です。バケットには n 個の値が格納され、バケット構造自体には k 個の要素があります。これは、別のソート済みベクターを返すこの実装で使われる空間量です。各値はすべてのバケットに複製されるのではなく、1つのバケットにだけ格納されるため、O(n * k) ではありません。