[アルゴリズム] バケットソート(PHP編)

2017年4月5日

PHP テクノロジー プログラミング 特集

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値で埋めてくれない為、今回はランダム値に5が数字として入っていない場合、仮登録する配列の5番目が登録されない状態となる。 この場合、どういう不具合が発生するかというと、 arr[1] arr[2] arr[3] arr[4] arr[6] これをcountしてみると、 count(arr) > 5 となる。 したがって、仮登録をfor文のインクリメントで実行した場合、loopが5回しか実行されず、6が処理されなくな事象があった。 これを回避するために、max値を取得して、for文につなげている。

関連リンク

wikipedia たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。