PHPの挿入ソートですが、javascriptでの苦戦をそのままコピーして対応しました。
CLASSを使って書いても良かったんですが、段階を踏みたかったので、今回はfunctionの羅列バージョンです。
でも、手慣れている言語で手慣れている書き方をしてもあまりおもしろくないんですよね。
やっぱり少し冒険しないと・・・個人的には仕事でも冒険するワクワク感がなんともたまらんのですよね。
ソースコード
<?php
/**
* [ insertSort ] 基本関数
*/
function insertSort($numbers){
// 数値配列を最初から順番に評価していく
for($i=1; $i<count($numbers); $i++){
// 確定数値リストを取得
$confirmLists = getConfirmLists($numbers , $i);
// 対象外の数値リストを取得
$lastLists = getLastLists($numbers , $i);
// 確定数値リストに挿入数値の挿入
$firstLists = setInsert($confirmLists , $numbers[$i]);
// リストの結合
$numbers = setUnionLists($firstLists , $lastLists);
}
return $numbers;
}
/**
* 確定数値リストに対象数値が挿入される位置を取得する
* [Summery]
* 返り値の手前に挿入される
* 数値リストよりも指定数値の方が大きい場合はnullが返る->数値の後ろに追加
* @param : confirmLists | 確定数値リスト
* @param : targetNum | 対象数値
* @return : number or null | 挿入位置番号
*/
function getInsertPlace($confirmLists , $targetNum){
$num = "null";
for($i=0; $i<count($confirmLists); $i++){
if($targetNum < $confirmLists[$i]){
$num = $i;
break;
}
}
return $num;
}
/**
* 全体数値リストから確定数値リストを取得
* @param : numbers | 全体数値リスト
* @param : targetNum | 対象数値番号
* @return : array | 確定数値リスト
*/
function getConfirmLists($numbers , $targetNum){
$arr = array();
for($i=0; $i<count($numbers); $i++){
if($i == $targetNum){
break;
}
array_push($arr , $numbers[$i]);
}
return $arr;
}
/**
* 数値リストの挿入
* @param : confirmLists | 確定数値リスト
* @param : targetNum | 対象数値
* @return : array | 数値入れ替え後の全体数値リスト
*/
function setInsert($confirmLists , $targetNum){
// 確定数値リストに対象数値が挿入される位置を取得する
$replaceNum = getInsertPlace($confirmLists , $targetNum);
// 挿入操作
$arr = array();
for($i=0; $i<count($confirmLists); $i++){
if($i === $replaceNum){
array_push($arr , $targetNum);
}
array_push($arr , $confirmLists[$i]);
}
// 挿入番号がnullの場合は入れ替えなし
if($replaceNum === "null"){
array_push($arr , $targetNum);
}
return $arr;
}
/**
* リストの結合
* @param : firstLists | 確定数値リスト
* @param : lastLists | 対象外数値リスト
* @return : array | 入れ替え後の全体数値リスト
*/
function setUnionLists($firstLists , $lastLists){
$arr = array();
if(count($firstLists) >0){
for($i=0; $i<count($firstLists); $i++){
array_push($arr , $firstLists[$i]);
}
}
if(count($lastLists) >0){
for($i=0; $i<count($lastLists); $i++){
array_push($arr , $lastLists[$i]);
}
}
return $arr;
}
/**
* 対象外の数値リストを取得
* @param : numbers
* @param : targetNum
* @return : array | 対象外リスト
*/
function getLastLists($numbers , $targetNum){
$arr = array();
for($i=$targetNum+1; $i<count($numbers); $i++){
array_push($arr , $numbers[$i]);
}
return $arr;
}
$res = insertSort(array(10,2,12,7,16,8,13));
echo join(",",$res);
echo PHP_EOL;
解説
少しユニットテストを意識したfunctionの書き方をしてみました。
テストコードを書くときは、その関数に想定の値を渡して望みの結果が返るかというコードをいくつも記述するだけなんですが、
重要なのは、想定値だけではなくて、想定外値としてわざとエラーが出るかどうかという記述も必要という事。
テストコードを書いてもいないのに偉そうに書くのはやめましょう。
nullの扱い
JSで使ったままPHPでもnullとして使っても良かったんですが、あえてstringの"null"という値を使って処理しています。
null撲滅員会なるものがあることを知って、最近nullに対して少しビビっているボクでした。
http://www.geocities.jp/mickindex/database/db_getout_null.html
コメントの扱い
ペチパーの人たちのよく書くようなコメント記述にしてみました。
関数に関してはparamとreturnという受け渡しと返り値をちゃんと型も踏まえて記述しておきましょう。
下手な仕様ドキュメントよりもよっぽど確実です。
更新もしやすいですしね。
実行
$ php insertSort.php
2,7,8,10,12,13,16
実は、JSからのコピーで何箇所もエラーが出まくって一発ではうまくいかなかったんですが、結果が伴っているので、これで良しとします。
詳細はざっくりですが、解説でご理解ください。
関連リンク
いろいろなプログラム言語でアルゴリズム学習
