バケットソートとは？仕組み・計算量・C++実装例をわかりやすく解説

バケットソート（バケット整列法）は、データ要素をあらかじめ用意した複数の「バケット（bucket）」に振り分けていくソート手法です。各バケットには値の範囲が似たデータが格納されるため、分散後に各バケットを個別に別のソートアルゴリズムで整列させ、最後にすべての要素を元のリストへ順番に集約することで、ソート済みの配列が得られます。

バケットソートの計算量

• 時間計算量：最良ケース・平均ケースで O(n + k)、最悪ケースで O(n²)

• 空間計算量：最悪ケースで O(nk)

入力と出力の例

入力:
未ソートのデータ列: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
ソート前の配列: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
出力:
ソート後の配列: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

アルゴリズム

bucketSort(array, size)

入力 − データの配列と、配列内の要素数

出力 − ソート済みの配列

Begin
    for i := 0 to size-1 do
        insert array[i] into the bucket index (size * array[i])
    done

    for i := 0 to size-1 do
        sort bucket[i]
    done

    for i := 0 to size -1 do
        gather items of bucket[i] and put in array
    done
End

C++による実装例

以下は、0 以上 1 未満の浮動小数点数を対象としたバケットソートの C++ 実装例です。各要素を size * array[i] のインデックスを持つバケットに格納し、各バケットを標準ライブラリの sort() で整列した後、順番に元の配列へ書き戻します。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void display(float *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void bucketSort(float *array, int size) {
    vector<float> bucket[size];
    for(int i = 0; i<size; i++) { // 要素をそれぞれのバケットに振り分ける
        bucket[int(size*array[i])].push_back(array[i]);
    }

    for(int i = 0; i<size; i++) {
        sort(bucket[i].begin(), bucket[i].end()); // 各バケット内をソート
    }

    int index = 0;
    for(int i = 0; i<size; i++) {
        while(!bucket[i].empty()) {
            array[index++] = *(bucket[i].begin());
            bucket[i].erase(bucket[i].begin());
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    float arr[n]; // 指定された要素数の配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    bucketSort(arr, n);

    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

このように、バケットソートはデータがある程度均一な範囲に分布している場合に特に有効で、平均的には線形時間に近い高速な整列を実現できます。一方で、データが特定のバケットに偏ると最悪ケースで O(n²) まで性能が劣化する点には注意が必要です。