Quicksort algorithm implementation in PHP

Quicksort algorithm implementation in PHP

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

Quicksort algorithm, as the name of it suggests, is yet another piece of code for sorting ( lists of ) items. The algorithm has been in use for nearly 60 years ( Anthony Hoare - its inventor - published it in 1961 ), and is still one of the fastest ways of sorting large lists of items ever devised.

Quicksort is a recursive algorithm. It divides an array of items into two smaller lists repeatedly till it reaches the point where either each of these lists contains one or no items. List of one or no elements is base case of the recursion (yup, the algorithm is recursive).

Each time before a given array is divided into two subarrays, items that are smaller than a boundary item (pivot) get moved over to the left of the array. On the other hand, larger items get shifted behind it. As a result of the operation (called partitioning), the pivot ends up in its final position in the list.

Partitioning can be performed according to various schemes. For example one can choose the first, the last or the middle item of the list as their pivot. More complex schemes also exist.

As far as I understand how it works works, quicksort algorithm turns an array into a binary tree and then traverses it recursively till it reaches all the leafs. Leafs consist of one-item-long lists while branches are lists of size two or longer.

Quicksort algorithm in PHP

My quicksort algorithm is implemented as a static class method. The method accepts two arguments at the maximum, first is an array of items to be sorted, second, optional, an anonymous functions. The function specifies how items in the list should be sorted.

The class also contains a private partitioning method. It works with indices ( as does qsort method ), chooses the middle item of the array as a pivot and returns current index of the privot once the smaller items have been moved over to positions preceding the pivot in the array ( sorting is done in ascending order by default ).

The quicksort algorithm implemetation


/* Class: RecursiveSort - recursive sort algorithms container
   Author : Sylwester Wojnowski
   WWW : wojnowski.net.pl
    
   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])

Final thoughts

My primary motivation behind implementing quicksort algorithm in PHP came from a whim of writing some non-run-of-the-mill piece of code that would allow me to play with sorting strings and dates in the programming language ( an article on the subject is in the pipeline ). In one of my previous articles I used my implementation of bubble sort algorithm for sorting stuff. Bubble sort is nice, but quicksort is still more interesting to deal with and a lot more fun to code at that.

I hope you enjoyed reading the article and perhaps learned something useful from it.

This post was updated on 13 Apr 2017 12:43:45

Tags:  php ,  recursion ,  sort 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2018 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Quicksort algorithm implementation in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/quicksort-algorithm-implementation-in-php