Quicksort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.


PHP implementation:

// Recursive version:
function quickSortRecursive( $arr, $left = 0 , $right = NULL )
{
 // when the call is recursive we need to change 
 //the array passed to the function yearlier
 static $array = array(); 
 if( $right == NULL )
  $array = $arr;

 if( $right == NULL )
  $right = count($array)-1;//last element of the array
 
 $i = $left;
 $j = $right;
 
 $tmp = $array[(int)( ($left+$right)/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 );
 
 // devide left side if it is longer the 1 element
 if( $left < $j )
  quickSortRecursive(NULL, $left, $j);
 
 // the same with the right side
 if( $i < $right )
  quickSortRecursive(NULL, $i, $right);

 // when all partitions have one element
 // the array is sorted
 
 return $array;
}



// 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;
}