BLOG ENTRY

PHPでマージソート(mergesort)のアルゴリズム

php

基本的なソートアルゴリズムであるマージソートをPHPで行う。

[php]
<?php

/*
* マージソートを行う
*/

//併合する関数
function mergeArr($left_arr, $right_arr) {

$result_arr = array();

$i = 0;
$j = 0;
$k = 0;

while ($i < count($left_arr) && $j < count($right_arr)) {

if ($left_arr[$i] < $right_arr[$j]) {
$result_arr[$k] = $left_arr[$i];
$i++;
$k++;
} else {
$result_arr[$k] = $right_arr[$j];
$j++;
$k++;
}
}

while ($i < count($left_arr)) {
$result_arr[$k] = $left_arr[$i];
$i++;
$k++;
}

while ($j < count($right_arr)) {
$result_arr[$k] = $right_arr[$j];
$j++;
$k++;
}

return $result_arr;
}

//マージソートを行う関数
function mergeSort($num_arr) {

if (count($num_arr) > 1) {
$left_arr = array_slice($num_arr, 0, ceil(count($num_arr)/2));
$right_arr = array_slice($num_arr, ceil(count($num_arr)/2));
return mergeArr(mergeSort($left_arr), mergeSort($right_arr));
} else {
return $num_arr;
}
}

$num_arr = array(2, 41, 105, 51, 86, 21, 75, 54, 46, 19);
$result_arr = mergeSort($num_arr);

var_dump($result_arr);

[/php]

終わり。

WRITE COMMENT


(required)


(required)


(required)

MENU

veltica creative of twitter