PHPのバケットソートは、Javascriptをそのままローカライズしたのではなく、少しだけ変更してある。
具体的には解説を読んでもらいたいが、配列定義や、その後の扱いなど、今まであまり気にしたことが無かった事象を発見した。
言語毎にこうした実行したときの挙動は違ってくるとは思うのだが、長年使っている言語でも、こうした事を今まで気がついていなかったことにビックリ！！
改めてこうしたプログラミングを地道に行うことと、ユニットテストを行うことの重要性を感じた。
ソース
<?php
function bucketSort($numbers){
// バケツ
$bucket = array();
$max = 0;
// バケツに入れる数字の数を足し込む
for($i=0; $i<count($numbers); $i++){
if(!count($bucket[$numbers[$i]])){
$bucket[$numbers[$i]] = array();
}
array_push($bucket[$numbers[$i]] , $numbers[$i]);
if($numbers[$i] > $max){$max = $numbers[$i];}
}
// 並び替え用配列
$arr = array();
// 数字の入っている数分配列データを作成
for($i=0; $i<=$max; $i++){
if(!count($bucket[$i])){continue;}
for($j=0; $j<count($bucket[$i]); $j++){
array_push($arr , $bucket[$i][$j]);
}
}
return $arr;
}
$numbers = array(1,1,3,2,4,6,1,2,4,6);
$res = bucketSort($numbers);
echo join($res) .PHP_EOL;
実行
$ php bucketSort.php
1112234466
解説
max値の取得
PHP言語では、配列に値を入れないと、key値で埋めてくれない為、今回はランダム値に５が数字として入っていない場合、仮登録する配列の５番目が登録されない状態となる。
この場合、どういう不具合が発生するかというと、
arr[1]
arr[2]
arr[3]
arr[4]
arr[6]
これをcountしてみると、
count(arr)
> 5
となる。
したがって、仮登録をfor文のインクリメントで実行した場合、loopが５回しか実行されず、6が処理されなくな事象があった。
これを回避するために、max値を取得して、for文につなげている。
関連リンク
wikipedia
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿