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

2017年3月13日

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

t f B! P L
マージソートは、配列操作のオンパレードなので、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

関連記事

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

このブログを検索

プロフィール

自分の写真
町田市, 東京都, Japan
プログラミングとサーバーを心の底から楽しむクリエーターです。 経営者であり、開発者でもありますが、得意としているのは、アイデア創出。

ブログ アーカイブ

QooQ