@blog.justoneplanet.info

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();


/**
 * bucketSort
 * @param {array} ary
 */
var bucketSort = function(ary){
    var hash = function(value){
        return Math.floor(value / 3);
    }// hash関数
    
    var bucket = [];
    for(var i = 0; i < ary.length; i++){
        if(!bucket[hash(ary[i])]){
            bucket[hash(ary[i])] = [ary[i]];
        }
        else{
            bucket[hash(ary[i])].push(ary[i]);
        }
    }// bucket配列に格納（各bucketは配列となっている）
    console.log(JSON.stringify(bucket));
    
    // 衝突したbucket内で挿入ソート
    for(var i = 0; i < bucket.length; i++){
        for(var i2 = 1; i2 < bucket[i].length; i2++){
            var value = bucket[i][i2];
            for(var i3 = i2 - 1; i3 >= 0; i3--){
                if(value <= bucket[i][i3]){
                    bucket[i][i3 + 1] = bucket[i][i3];
                }
                else{
                    break;
                }
            }
            bucket[i][i3 + 1] = value;
        }
    }
    console.log(JSON.stringify(bucket));
    
    // bucketの先頭の要素から取り出し、元の配列を上書きする
    var store = 0;
    for(var i = 0; i < bucket.length; i++){
        if(bucket[i]){
            for(var i2 = 0; i2 < bucket[i].length; i2++){
                ary[store++] = bucket[i][i2];
            }
        }
    }
}


bucketSort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
// ハッシュ関数と要素の分布によって衝突することもある
// 以下がハッシュ関数に対して理想的な分布だった場合
// var a = [15, 21, 9, 27, 3, 12, 18, 24, 6, 0];
// [[0],[3],[6],[9],[12],[15],[18],[21],[24],[27]]
// 以下が衝突が起こった場合
// var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
// [[0,1,2],[3,4,5],[6,7,8],[9]]
// 衝突が起こると挿入ソートの回数が増えて性能が低下する

■特性

• 高速ハッシュ関数を使って、要素が一様に分割できる必要がある