Quicksort non-recursive.php

From Algorithmist
Jump to: navigation, search

This is an implementation of Quicksort in PHP. This algorithm is non-recursive. Algorithm is a modified version available here [1].

// Non recursive version:
function quickSort( $array )
{
 $cur = 1;
 $stack[1]['l'] = 0;
 $stack[1]['r'] = count($array)-1;
 
 do 
 {
  $l = $stack[$cur]['l'];
  $r = $stack[$cur]['r'];
  $cur--;
 
  do
  {
   $i = $l;
   $j = $r;
   $tmp = $array[(int)( ($l+$r)/2 )];
 
   // partion the array in two parts.
   // left from $tmp are with smaller values,
   // right from $tmp are with bigger ones
   do
   {
    while( $array[$i] < $tmp )
     $i++;
 
    while( $tmp < $array[$j] ) 
     $j--;
 
    // swap elements from the two sides 
    if( $i <= $j )
    {
     $w = $array[$i];
     $array[$i] = $array[$j];
     $array[$j] = $w;
 
     $i++;
     $j--;
    }
 
   }while( $i <= $j );
 
 
   if( $i < $r )
   {
    $cur++;
    $stack[$cur]['l'] = $i;
    $stack[$cur]['r'] = $r;
   }
   $r = $j;
 
  }while( $l < $r );
 
 }while( $cur != 0 );
 
 return $array;
}