BLOG ENTRY

previousnext

PHPでクイックソートのアルゴリズム

php

基本的なソートアルゴリズムのクイックソートのプログラムメモ。

  1. <?php
  2.  
  3.     /*
  4.     * クイックソート
  5.     * $numArr    = ソートする配列
  6.     * $left      = 開始位置（0で決め打ち）
  7.     * $right     = 終了位置（$numArrの要素数）
  8.     * $order     = ソートの昇順(ASC)・降順(DESC) デフォルトは昇順
  9.     */
  10.     function quickSort(&$numArr, $left = 0, $right, $order = "ASC") {
  11.    
  12.         //要素数が1以下であれば
  13.         //ソートをする必要がないので処理を終了する。
  14.         if ($left>= $right) {
  15.             return;
  16.         }
  17.        
  18.         swap ($numArr, $left, ceil(($left+$right)/2));
  19.         $last = $left;
  20.        
  21.         for ($i=$left+1; $i<=$right; $i++) {
  22.  
  23.             if ($order == "ASC") {
  24.            
  25.                 if ($numArr[$i] <$numArr[$left]) {
  26.                     swap($numArr, ++$last, $i);
  27.                 }
  28.                
  29.             } else {
  30.            
  31.                 if ($numArr[$i]>$numArr[$left]) {
  32.                
  33.                     swap($numArr, ++$last, $i);
  34.                    
  35.                 }
  36.             }
  37.         }
  38.        
  39.         swap($numArr, $left, $last);
  40.         quickSort($numArr, $left,   $last-1, $order = $order);
  41.         quickSort($numArr, $last+1, $right,  $order = $order);
  42.     }
  43.     //要素を入れ替える関数
  44.     function swap(&$v, $i, $j) {
  45.         $temp  = $v[$i];
  46.         $v[$i] = $v[$j];
  47.         $v[$j] = $temp;
  48.     }
  49.  
  50.     //ソート対象の配列
  51.     $numArr    = array(92, 15, 26, 86, 105, 54, 29, 42, 75);
  52.    
  53.     echo "ソート前";
  54.     echo "<pre>";
  55.     print_r($numArr);
  56.     echo "</pre>";
  57.    
  58.     quickSort($numArr, 0, count($numArr)-1, $order="DESC");
  59.    
  60.     echo "ソート後";
  61.     echo "<pre>";
  62.     print_r($numArr);

以上。

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

WRITE COMMENT


（required）


（required）


（required）

MENU