[アルゴリズム] バケットソート（Javascript編）
今回のアルゴリズム・ソースコードは今までの流れと少し変わっています。
これまでは、異なる乱数でのソートプログラムで、同数が存在していても、あまり気にしなかったのですが、
今回のバケットソートというのは、同一の数字をグループ化することで、ある一定のグルーピングされている数字がランダムに並んだ数字郡を
揃えて表示するというものです。
使い方は、なかなかイメージできないですが、とりあえず、比較的有名なソートアルゴリズムという事で、シリーズに加えたいと思います。
ソース
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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, 1, 2, 2, 3, 4, 4, 6, 6] |
解説
バケツ処理
バケツ配列を作って、そこには整数が入るという事が条件なので、乱数にマイナス値や、少数値が入っていると、
正常に動作しない。
バケツから１次元配列の作成
バケツには、同じ数字が入っている個数を値としていれているので、nullまたは0の状態のバケツは、処理をしない為、continueしている。
このソートの問題点
さらに、乱数の数字の幅が大きすぎると、単純にそれだけでメモリを食いつぶしてしまう。
このソートの使いみちとして、近似値の数値または、rangeが似通っているグループ郡に対して、処理することが前提になる。
ソース改修
単純に今回のプログラムでは、汎用性が少ないので、下記のように改修してみました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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の乱数をバケツ処理するという再帰処理的に行うことで、メモリ値を抑えて処理することができるようになる訳です。
でも、やはり、マイナス値や、小数点なども処理できるようにしなければイケないかな？