[アルゴリズム] マージソートのプログラミング(PHP編)

2017年3月13日

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

マージソートは、配列操作のオンパレードなので、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つに分割して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

関連記事

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

このブログを検索

ごあいさつ

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