医学生わくばの欲張り技術ブログ

〜E資格を取りに行く!〜

【アルゴリズム(JS実装)】Bucket Sort

 どうも、わくばです!

 

 今日はBucket Sortを勉強しました。バケツを用いた分割統治アルゴリズムで、Counting Sort の一般化と考えられます。実際、バケツサイズを1とすると同じ値のものだけが同じバケツに集約されていくので、Couting Sortと同様の処理になります。

 バケツに分割して、それぞれのバケツでソートを実行し、統合するという典型的な仕組みです。

 

コードはこんな感じです。 

//bucketSize : バケット一個あたりの要素数
const bucketSort = (array, bucketSize = 5) => { 
    if (array.length < 2) {
        return array;
    }

    //以前記事にしたinsertionSort参照
    const insertionSort = array => {
        for (let i = 1; i < array.length; i++) { 
            let j = i; 
            let temp = array[i]; 
            while (j > 0 && array[j - 1]> temp)  { 
                array[j] = array[j - 1]; 
                j--;
            }
            array[j] = temp; 
        }
        return array;
    };

    //バケットを作成
    const createBuckets = (array, bucketSize) => {
        const minVal = Math.min(...array);
        const maxVal = Math.max(...array);
        //バケット数を計算
        const bucketCount = Math.floor(
            (maxVal - minVal) / bucketSize
            ) + 1; 
        const buckets = [];
        for (let i = 0; i < bucketCount; i++) { 
            buckets[i] = [];
        }
        for (let i = 0; i < array.length; i++) { 
            //ある要素を何個目のバケットに入れるか計算
            const bucketIndex = Math.floor(
                (array[i] - minVal) / bucketSize
                ); 
            buckets[bucketIndex].push(array[i]); 
        }
        return buckets;
    }

    const sortBuckets = buckets => {
        //バケット内をソート
        return buckets.reduce((acc,cur)=>{
            if (cur != null) {
                insertionSort(cur); 
                acc.push(...cur);
            }
            return acc;
        },[])
    }

    //createBucketsを実行
    const buckets = createBuckets(array, bucketSize); 
    //sortBucketsを実行
    return sortBuckets(buckets); 
}

const array = [1,3,6,78,9,65,4,3,2,5,7,7,5,5,3,9,3]
console.log(bucketSort(array));

>>>[
1, 2, 3, 3, 3, 3, 4,
5, 5, 5, 6, 7, 7, 9,
9, 65, 78

 Complexityは結構複雑で、いろいろ調べた結果Wikiが一番わかりやすかったので引用させていただきます。

 以下はAverage Complexityの部分の引用です。

Consider the case that the input is uniformly distributed. The first step, which is initialize the buckets and find the maximum key value in the array, can be done in  time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs . Assume insertion sort is used to sort each bucket, then the third step costs , where  is the length of the bucket indexed . Since we are concerning the average time, the expectation  has to be evaluated instead. Let  be the random variable that is  if element  is placed in bucket , and  otherwise. We have . Therefore,

The last line separates the summation into the case  and the case . Since the chance of an object distributed to bucket  is  is 1 with probability  and 0 otherwise.

With the summation, it would be

Finally, the complexity would be .

The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires  time. Therefore, the total complexity is . Note that if k is chosen to be , then bucket sort runs in  average time, given a uniformly distributed input.[1]

  はバケットのサイズのことで、はバケットサイズの二乗を平均しています。二乗なのはInsertion Sortを用いているためです。なのでは、k個のバケットのComplexityを合計したものです。

 最後の結合も計算に入れて最終的にはと算出されています。

 

 

 今日は以上です。

 

 では。