今回のアルゴリズム・ソースコードは今までの流れと少し変わっています。
これまでは、異なる乱数でのソートプログラムで、同数が存在していても、あまり気にしなかったのですが、
今回のバケットソートというのは、同一の数字をグループ化することで、ある一定のグルーピングされている数字がランダムに並んだ数字郡を揃えて表示するというものです。
使い方は、なかなかイメージできないですが、とりあえず、比較的有名なソートアルゴリズムという事で、シリーズに加えたいと思います。
ソース
function bucketSort(numbers){
// バケツ
var bucket = [];
// バケツに入れる数字の数を足し込む
for(var i=0; i<numbers.length; i++){
if(typeof bucket[numbers[i]] == "undefined"){
bucket[numbers[i]] = 1;
}
else{
bucket[numbers[i]]++;
}
}
// 並び替え用配列
var arr = [];
// 数字の入っている数分配列データを作成
for(var i=0; i<bucket.length; i++){
if(!bucket[i]){continue}
for(var j=0; j<bucket[i]; j++){
arr.push(i);
}
}
return arr;
}
var numbers = [1,1,3,2,4,6,1,2,4,6];
var res = bucketSort(numbers);
console.log(res);
実行
[1, 1, 1, 2, 2, 3, 4, 4, 6, 6]
解説
バケツ処理
バケツ配列を作って、そこには整数が入るという事が条件なので、乱数にマイナス値や、少数値が入っていると、
正常に動作しない。
バケツから１次元配列の作成
バケツには、同じ数字が入っている個数を値としていれているので、nullまたは0の状態のバケツは、処理をしない為、continueしている。
このソートの問題点
さらに、乱数の数字の幅が大きすぎると、単純にそれだけでメモリを食いつぶしてしまう。
このソートの使いみちとして、近似値の数値または、rangeが似通っているグループ郡に対して、処理することが前提になる。
ソース改修
単純に今回のプログラムでは、汎用性が少ないので、下記のように改修してみました。
function bucketSort(numbers){
// バケツ
var bucket = [];
// バケツに入れる数字の数を足し込む
for(var i=0; i<numbers.length; i++){
if(typeof bucket[numbers[i]] == "undefined"){
bucket[numbers[i]] = [];
}
bucket[numbers[i]].push(numbers[i]);
}
// 並び替え用配列
var arr = [];
// 数字の入っている数分配列データを作成
for(var i=0; i<bucket.length; i++){
if(typeof bucket[i] == "undefined" || !bucket[i].length){continue}
for(var j=0; j<bucket[i].length; j++){
arr.push(bucket[i][j]);
}
}
return arr;
}
var numbers = [1,1,3,2,4,6,1,2,4,6];
var res = bucketSort(numbers);
console.log(res);
変更点は、バケツ処理のところで、中に入っている個数を配列で格納するようにした。
整数の格納という条件は変わらないが、少し柔軟なグルーピングができるようになる。
例えば、0 - 100までの乱数がある場合、バケツが１００個必要になってしまうが、
最初の処理として、10,20,30...という風に１０のバケツには10-19、20のバケツには20-29という風に、まとめて入れ込むことで、
さらにバケツの中身を10-19の乱数をバケツ処理するという再帰処理的に行うことで、メモリ値を抑えて処理することができるようになる訳です。
でも、やはり、マイナス値や、小数点なども処理できるようにしなければイケないかな？
関連リンク
wikipedia
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿