マージソートは、配列操作のオンパレードなので、C言語やShellをコーディングするのが、非常に難しそうだが、PHPは、関数パラダイスなので、こうした処理は得意な言語です。
でも、あまりPHPに特価した関数を使うのは好きではないので、できるだけ自分で効率的な関数が書けると、PHPモジュールのバージョンアップの時に、いきなり関数の仕様が変わったときや、使えなくなった時などには、非常に堅牢なシステムになるはずなので、こうしたレガシーの考え方はシステム開発においては重要だと思われる。
最近のWEBシステム開発ではこうした思考が求められているのではないかな？
ソースコード
<?php
// 分割位置の取得
function midPoint($nums){
return (int)((count($nums) / 2) + 0.5);
}
// condition
function setMarge($arr1 , $arr2){
$arr = array();
while(count($arr1) || count($arr2)){
if(count($arr1) == 0){
array_push($arr , array_shift($arr2));
}
else if(count($arr2) == 0){
array_push($arr , array_shift($arr1));
}
else if($arr1[0] > $arr2[0]){
array_push($arr , array_shift($arr2));
}
else{
array_push($arr , array_shift($arr1));
}
}
return $arr;
}
// 配列を2つに分割して２つの値の場合それをソートする
function mergeSort($numbers){
if(!count($numbers)){
return array();
}
else if(count($numbers) == 1){
}
else if(count($numbers) == 2){
if($numbers[0] > $numbers[1]){
$tmp = $numbers[0];
$numbers[0] = $numbers[1];
$numbers[1] = $tmp;
}
}
else{
$midNum = midPoint($numbers);
$arr1 = array_slice($numbers , 0 , $midNum);
$arr2 = array_slice($numbers , $midNum);
$arr1 = mergeSort($arr1);
$arr2 = mergeSort($arr2);
$numbers = setMarge($arr1 , $arr2);
}
return $numbers;
}
$numbers = array(20,10,2,12,7,16,8,13,1);
$numbers = mergeSort($numbers);
print_r($numbers);
実行
$ php mergeSort.php
Array
(
[0] => 1
[1] => 2
[2] => 7
[3] => 8
[4] => 10
[5] => 12
[6] => 13
[7] => 16
[8] => 20
)
解説
PHP使用したの配列操作
# 先頭の値を取り出す
$arr = array(1,2,3,4,5);
$arr1 = array_shift($arr);
> $arr = [2,3,4,5]
> $arr1= [1]
# 追加
$arr = array();
array_push($arr , 1);
> $arr = [1]
# 配列を部分的に取り出す
$numbers = array(1,2,3,4,5);
$arr = array_slice($numbers , 2 , 2)
> $arr = [3,4]
$arr = array_slice($numbers , 2)
> $arr = [3,4,5]
小数点数値の四捨五入処理
(int)((count($nums) / 2) + 0.5);
端数の数値に0.5を足しこんでintで整数化（端数切り捨て）をすれば、四捨五入処理になる。
PHPのintは(int)とカッコで囲むようにしよう。
処理速度
MacBookPro Corei7 3.3GHzにHomebrewでインストールしたPHPで実行したんだが、下記のような計測値となった。
他言語と比較してみるといいかも。
real 0m0.078s
user 0m0.058s
sys 0m0.011s
関連記事
たくさんのプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿