C++でバケットソートを実装する方法【アルゴリズムとサンプルコードを解説】

バケットソートとは

バケットソート(Bucket Sort)は、データ要素を複数の「バケット(桶)」に分配してから整列を行うソート手法です。各バケットには性質の似たデータが格納され、分配後は各バケット内を別のソートアルゴリズム(ここでは標準ライブラリの sort)で整列します。最後にすべてのバケットの要素を元の配列へ順番に集めることで、全体がソートされた状態になります。

このアルゴリズムは、入力データが0.0以上1.0未満のような一様な分布に従う場合に特に高い性能を発揮します。

バケットソートの計算量

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

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

※ n は要素数、k はバケットの数を表します。

入出力の例

入力 − ソート前のデータ列: 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(配列, 要素数)

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

出力: ソート済みの配列

Begin
   for i := 0 to size-1 do
      array[i] をバケット番号 (size * array[i]) に挿入する
   done
   for i := 0 to size-1 do
      bucket[i] をソートする
   done
   for i := 0 to size-1 do
      bucket[i] の要素を取り出し、配列に順に格納する
   done
End

C++サンプルコード

#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);
}

コードのポイント

各要素は「要素数 × 要素の値」をインデックスとしてバケットに振り分けられます。入力値が0.0以上1.0未満の範囲に収まっている前提のため、計算されるインデックスは必ず0以上・要素数未満になります。その後、各バケット内で sort() を用いて整列し、先頭のバケットから順に元の配列へ書き戻すことで、全体のソートが完成します。

実行結果

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