JavaScriptでバケットソートを実装する方法を解説！サンプルコード付き

バケットソート（Bucket Sort）は、サイズnの配列を、特定の値の範囲を持つk個の「バケット（bucket）」と呼ばれるグループに分割することで動作するソートアルゴリズムです。

その後、各バケットは別のソートアルゴリズムを使って個別に整列されます。この際、入力データの規模に応じて最適なソートアルゴリズムを選択できるのが特徴です。

このアルゴリズムの手順は以下のように説明できます。

アルゴリズムの流れ

1. 初期の bucketSort 関数を作成する
2. i、min、max、バケットサイズ用の変数を用意する
3. 最小値と最大値を求める
4. バケットの数を決定する
5. 各値を適切なバケットへ振り分ける
6. 各バケット内をソートする

実装例

実際のコードは次のようになります。

const arr = [32, 6, 34, 4, 78, 1, 6767, 4, 65, 34, 879, 7];
const bucketSort = arr => {
    if (arr.length === 0) {
        return arr;
    }
    let i,
    minValue = arr[0],
    maxValue = arr[0],
    bucketSize = 5;
    arr.forEach(function (currentVal) {
        if (currentVal < minValue) {
            minValue = currentVal;
        } else if (currentVal > maxValue) {
            maxValue = currentVal;
        }
    })
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    let allBuckets = new Array(bucketCount);
    for (i = 0; i < allBuckets.length; i++) {
        allBuckets[i] = [];
    }
    arr.forEach(function (currentVal) {
        allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
    });
    arr.length = 0;
    allBuckets.forEach(function(bucket) {
        insertion(bucket);
        bucket.forEach(function (element) {
            arr.push(element)
        });
    });
    return arr;
}
const insertion = arr => {
    let length = arr.length;
    let i, j;
    for(i = 1; i < length; i++) {
        let temp = arr[i];
        for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = temp;
    }
    return arr;
};
console.log(bucketSort(arr));

実行結果

コンソールには以下のように出力されます。

[
    1, 4, 4, 6,
    7, 32, 34, 34,
    65, 78, 879, 6767
]

コードのポイント

この実装では、まず配列全体から最小値と最大値を取得し、その差分をもとに必要なバケット数を計算しています。各要素は (currentVal - minValue) / bucketSize の計算によって、どのバケットに入るかが決まります。

最後に、各バケット内の要素を挿入ソート（insertion sort）で整列し、すべてのバケットを先頭から順に連結することで、完全にソートされた配列が完成します。