■実装
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]]
// 衝突が起こると挿入ソートの回数が増えて性能が低下する
■特性
- 高速ハッシュ関数を使って、要素が一様に分割できる必要がある