PHPでクイックソートを書いてみた

クイックソートを書いてみたら意外と手こずった。
最終的にはCのコードをチラ見して書いたが良い復習になった。
ソートを真面目に考えたのは考えて見れば基本情報を受けたとき以来か。

どのタイミングで左右のポインタとなる添字が入れ替わるか、
その後の再帰処理を呼び出す際の引数をどうするか、でちょっとハマった。

  <?php
   function swap($arr, $x, $y){
       $tmp = $arr[$x];
       $arr[$x] = $arr[$y];
       $arr[$y]  = $tmp;
       return $arr;
   }
  
   function qsort(&$arr, $left, $right){
 
    $pl = $left;
    $pr = $right;
 
    $pivot = $arr[($left + $right)/2];
 
    print_r($arr);
   // echo "left:" . $left."\n";
   // echo "right:" . $right."\n";
   // echo "pivot:" . $pivot."\n";
 
  
    while($pl < $pr){
     while($arr[$pr] > $pivot){
          echo '$prをデクリメント(while内)'.$pr."\n";
          $pr--;
      }
      while($arr[$pl] < $pivot){
          echo '$plをインクリメント(while内)'.$pl."\n";
          $pl++;
      }
 
      //if($arr[$left] != $arr[$right]){
        if($pl <= $pr){
         echo 'swap $arr[$left]:'.$arr[$pl]."\n";
         echo 'swap $arr[$right]:'.$arr[$pr]."\n";
         $arr = swap($arr, $pl, $pr);
      echo '$plをインクリメント'.$pl."\n";
      $pl++;
      echo '$prをデクリメント'.$pr."\n";
      $pr--;
  }
  
}
   if($left < $pr){
  //    echo "***left処理***\n";
  //    echo '$left:' . $left ."\n";
  //    echo '$pr:' . $pr ."\n";
        qsort($arr,$left, $pr);
    }
 
    if($right > $pl){
  //  echo "***right処理***\n";
  //  echo '$right:' . $right ."\n";
  //  echo '$pl:' . $pl ."\n";
      qsort($arr,$pl,$right);
    }
  }//end func
 
  //$arr = array(4,3,2,1);
    //$arr = array(40, 50, 80, 70,100,10,30,20,90);
    $arr = array(1,2,1,2,1,2,1,2,1,1,1,1,2,2,2,2,2);
    $size = sizeof($arr);
 
    echo "***before sort***\n";
    echo print_r($arr);
    echo "***begin sort***\n";
    qsort($arr,0,$size-1);
    echo "***after sort***\n";