Quicksort algorithm implementation in PHP

Created:13 Apr 2017 09:56:52 , in  Maths

Quicksort algorithm implementation - as ugly as it gets.

The quicksort algorithm implemetation in PHP

/* Class: RecursiveSort - recursive sort algorithms container
    
   Methods: 
     public static qsort($list, [$compare])
       Description:
         sort items in $list  
       Parameters: 
         $list array - items (integers, strings, arrays, objects)
         [$compare] - anonymous function - function used for comparisons,
           accepts two arguments, compares them and returns bool true or false.         
*/

class RecursiveSort{

  private static $qsort_list = null; 
  private static $qsort_a = null;
  private static $qsort_count = -1;
  private static $qsort_counter = -1;
  private static $qsort_first = -1;
  private static $qsort_last = -1;
  private static $qsort_needs_reset = false;
  
  private static function qsort_reset(){
    self::$qsort_a = null;
    self::$qsort_count = -1;
    self::$qsort_counter = -1;
    self::$qsort_first = -1;
    self::$qsort_last = -1;
    self::$qsort_needs_reset = false;
  }
 
  private static function qsort_partition($qsort_list,$first,$last,$compare = false){ 
    $l = $qsort_list;
    
    if(!$compare){ $compare = function($a,$b){ return $a < $b; }; }
    
    $n = $last - $first + 1;
   
    $i = $first;

    # find pivot index
    $pi = $i + ( $n % 2 === 0 ? (($n + 2) / 2) : (($n + 1) / 2) ) - 1;

    # partition
    while( $i <= $last ){
      if( $compare($l[$i], $l[$pi]) ){
        if( $i - $pi > 1 ){
          $tmp = $l[$i];
          $l[$i] = $l[$pi+1];
          $l[$pi+1] = $l[$pi];
          $l[$pi] = $tmp;
          $pi++;  
        } else 
          if ( $i - $pi === 1 ){
            $tmp = $l[$pi];
            $l[$pi] = $l[$i];
            $l[$pi+1] = $tmp;
            $pi++;
          }    
      } else {  
        if($i < $pi){
          $tmp = $l[$i];
          $l[$i] = $l[$pi];
          $l[$pi] = $tmp;
          $pi = $i; 
        }
      }
      $i++;
    }
 
    self::$qsort_a = $l;
  
    return $pi;
  }
  
  public static function qsort($a,$compare = false){
      
    # reset variables if necessary  
    if(self::$qsort_needs_reset){ self::qsort_reset(); }
    
    # initial setup
    if(is_null(self::$qsort_a)){
      self::$qsort_a = $a;
      self::$qsort_first = 0;
      self::$qsort_count = count(self::$qsort_a);
      self::$qsort_last = self::$qsort_count - 1;
      self::$qsort_counter = 0;
    }    
     
    # leaf found 
    if (self::$qsort_last - self::$qsort_first + 1 === 1) {
      self::$qsort_counter++;
    }  
    
    # branch found     
    if ( self::$qsort_last - self::$qsort_first + 1 > 1 ){
      
      # partition according to $compare function
      $pi = self::qsort_partition(self::$qsort_a,self::$qsort_first,self::$qsort_last,$compare);

      # leaf found
      self::$qsort_counter++;

      #set bounds for left and right array 
      $first_l = self::$qsort_first;
      $last_l = $pi - 1;
      $first_r = $pi + 1;
      $last_r = self::$qsort_last;
     
      # deal with left branch / leaf
      self::$qsort_first = $first_l;
      self::$qsort_last = $last_l;  
      self::qsort(self::$qsort_a,$compare);  
      
      # deal with right branch / leaf
      self::$qsort_first = $first_r;
      self::$qsort_last = $last_r;
      self::qsort(self::$qsort_a,$compare);
    }

    # all leafs found
    if( self::$qsort_count === self::$qsort_counter ){
      self::$qsort_needs_reset = true;
    }
    
    return self::$qsort_a;
  }
}

Use examples

Sorting integers in ascending order:

RecursiveSort::qsort(array(-8,3,1,2,-17,0,0,25));
=> array(-17,-8,0,0,1,2,3,25)

Sorting integers in descending order using a function:

RecursiveSort::qsort(array(-8,3,1,2,-17,0,0,25),function($a,$b){return $a > $b;})
=> array(25,3,2,1,0,0,-8,-17)

Sorting arrays in ascending order:

RecursiveSort::qsort(
  array(
    array(4,2),
    array(3,5),
    array(5,2)
  ),
  function($a,$b){
    return $a[0] * $b[1] < $a[0] * $b[1];
  }
);
=> array(array(3,5),array(5,2),array(4,2))

Sorting objects in ascending order:

$engines = array(
  (object)array("capacity" => 1000.50),
  (object)array("capacity" => 800),
  (object)array("capacity" => 2050),
);

RecursiveSort::qsort(
  $engines,
  function($a,$b){
    return $a -> capacity < $b -> capacity;
  }
);
=> array($engines[1],$engines[0],$engines[2])

This post was updated on 06 Oct 2021 21:36:30

Tags:  php ,  recursion ,  sort