Quicksort algorithm implementation in PHP

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 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.

Copyrights

©Copyright, 2022 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

Add Comment

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]


I constent to processing my data given through this form for purposes of a reply by the administrator of this website.

Recent Comments

Nobody has commented on this post yet. Be first!