Read 229 times | Created 2013-02-12 03:00:39 | Updated 2013-02-12 03:02:49 | | |

 

<pre>
<?php
/*********************************  
FILENAME  : sort.php  
CREATE BY  : cahya dsn  
PURPOSE   : sort algorithm implementation  
CREATE DATE : 2013-02-12  
**********************************/
$a=array(9,3,5,1,2,8,7,4,6);
//====================
echo "//insertion sortn";
function insertion_sort($a){
  $n=count($a);
  for ($i = 1;$i<$n;$i++){
    for ($k = $i; $k>0; $k--) {
      if($a[$k]<$a[$k-1]){
        $dummy=$a[$k];
        $a[$k]=$a[$k-1];
        $a[$k-1]=$dummy;
      }
    }
  }
  return $a;
}
print_r(insertion_sort($a));
//====================
echo "//selection sortn";
function selection_sort($a){
  $n=count($a);
  for ($i = 0;$i<$n;$i++){
    $k = $i;
    for ($j = $i+1;$j<$n;$j++){
      if ($a[$j] < $a[$k]) $k = $j;
    }   
    $dummy=$a[$i];
    $a[$i]=$a[$k];
    $a[$k]=$dummy;
  }
  return $a;
}
print_r(selection_sort($a));
//====================
echo "//bubble sortn";
function bubble_sort($a){
  $n=count($a);
  for ($i = 0;$i<$n;$i++){
      for ($j = $n-1;$j>$i;$j--){
          if ($a[$j] < $a[$j-1]){ 
              $dummy=$a[$j];
              $a[$j]=$a[$j-1];
              $a[$j-1]=$dummy;
          }
      }    
  }
  return $a;
}
print_r(bubble_sort($a));
//====================
echo "//quick sortn";
function quick_sort($a) {
    if(!count($a)) return $a;
    $pivot= $a[0];
    $low = $high = array();
    $n = count($a);
    for($i=1; $i < $n; $i++) {
        if($a[$i] <= $pivot) {
            $low [] = $a[$i];
        } else {
            $high[] = $a[$i];
        }
    }
    return array_merge(quick_sort($low), array($pivot), quick_sort($high));
}
print_r(quick_sort($a));
//====================
echo "//merge sortn";
function merge_sort ($a)
{
  if (count($a) <= 1 ) return $a;
  $left  = merge_sort(array_splice($a,floor(count($a) / 2)));
  $right = merge_sort($a);
  $result = array();
  while (count($left) > 0 && count($right) > 0)
  {
      if ($left[0] <= $right[0])
          array_push($result, array_shift($left));
      else
          array_push($result, array_shift($right));
  }
  while (count($left) > 0)
      array_push($result, array_shift($left));
  while (count($right) > 0)
      array_push($result, array_shift($right));  
  return $result;
}
print_r(merge_sort($a));
//====================
echo "//shell sortn";
function shell_sort($a)
{
 $n=count($a);
   $k=0;
   $gap[0]=(int) ($n / 2);
   while($gap[$k]>1)
   {
     $k++;
     $gap[$k]=(int)($gap[$k-1]/2);
   }
    for($i=0;$i<=$k;$i++)
   {
   $step=$gap[$i];
     for($j=$step;$j<$n;$j++)
     {
       $temp=$a[$j];
       $p=$j-$step;
       while($p>=0 && $temp<$a[$p])
       {
         $a[$p+$step]=$a[$p];
         $p=$p-$step;
       }
       $a[$p+$step]=$temp;
     }
   }
   return $a;
}
print_r(shell_sort($a));
//==================
echo "//heap sortn";
function build_heap(&$a, $i, $t){
  $tmp_var = $a[$i];    
  $j = $i * 2 + 1;
  while ($j <= $t)  {
   if($j < $t)
    if($a[$j] < $a[$j + 1]) {
     $j = $j + 1; 
    }
   if($tmp_var < $a[$j]) {
    $a[$i] = $a[$j];
    $i = $j;
    $j = 2 * $i + 1;
   } else {
    $j = $t + 1;
   }
  }
  $a[$i] = $tmp_var;
}

function heap_sort(&$a) {
  $init = (int)floor((count($a) - 1) / 2);
  for($i=$init; $i >= 0; $i--){
   $count = count($a) - 1;
   build_heap($a, $i, $count);
  }
  for ($i = (count($a) - 1); $i >= 1; $i--)  {
   $tmp_var = $a[0];
   $a[0] = $a[$i];
   $a[$i] = $tmp_var;
   build_heap($a, 0, $i - 1);
  }
}
heap_sort($a);
print_r($a);
?>