BLOG ENTRY

previousnext

PHPでマージソート（mergesort）のアルゴリズム

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

  1. <?php
  2.  
  3. /*
  4. * マージソートを行う
  5. */
  6.  
  7. //併合する関数
  8. function mergeArr($left_arr, $right_arr) {
  9.  
  10.     $result_arr = array();
  11.    
  12.     $i = 0;
  13.     $j = 0;
  14.     $k = 0;
  15.    
  16.     while ($i <count($left_arr) && $j <count($right_arr)) {
  17.    
  18.         if ($left_arr[$i] <$right_arr[$j]) {
  19.             $result_arr[$k] = $left_arr[$i];
  20.             $i++;
  21.             $k++;
  22.         } else {
  23.             $result_arr[$k] = $right_arr[$j];
  24.             $j++;
  25.             $k++;
  26.         }
  27.     }
  28.    
  29.     while ($i <count($left_arr)) {
  30.         $result_arr[$k] = $left_arr[$i];
  31.         $i++;
  32.         $k++;
  33.     }
  34.    
  35.     while ($j <count($right_arr)) {
  36.         $result_arr[$k] = $right_arr[$j];
  37.         $j++;
  38.         $k++;
  39.     }
  40.    
  41.     return $result_arr;
  42. }
  43.  
  44. //マージソートを行う関数
  45. function mergeSort($num_arr) {
  46.  
  47.     if (count($num_arr)> 1) {
  48.         $left_arr  = array_slice($num_arr, 0, ceil(count($num_arr)/2));
  49.         $right_arr = array_slice($num_arr, ceil(count($num_arr)/2));
  50.         return mergeArr(mergeSort($left_arr), mergeSort($right_arr));
  51.     } else {
  52.         return $num_arr;
  53.     }
  54. }
  55.  
  56. $num_arr = array(2, 41, 105, 51, 86, 21, 75, 54, 46, 19);
  57. $result_arr = mergeSort($num_arr);
  58.  
  59. var_dump($result_arr);



終わり。

comments(0)
はてなブックマークに追加 del.icio.usに追加 ライブドアクリップに追加 POOKMARK Airlinesに追加 Buzzurl（バザール）に追加 ニフティクリップに追加
DATE2008.07.19

WRITE COMMENT


（required）


（required）


（required）

MENU