Recursive bubble sort algorithm in PHP

Recursive bubble sort algorithm in PHP

Created:06 Apr 2017 17:48:19 , in  Maths

In this article I'm going to take a quick look at arranging elements of a list in a chosen order, or simply speaking - sorting, with a twist, though. Many algorithms have been devised for the purpose of sorting over the last sixty or so years. Arguably, one of the oldest and more popular of them is bubble sort.

Bubble sort is a stable but also inefficient algorithm when it comes to sorting large list. But hey, rather than for blazingly fast execution I'm looking to play with some PHP features here now.

Moreover, bubble sort is a fairly simple algorithm. It can be implemented really quick using recursion (a twist;) and anonymous functions ( it's a pity they can't be passed as optional arguments to a function in PHP, though - another, negative twist this time ).

Getting to nitty-gritty

My recursive implementation of bubble sort algorithm is a static class method. Apart from this it differs little from PHP sort function, in particular in terms of how it sorts.

As for arguments, it accepts three of them ( the third one is not really usable, though - yet another twist ;).

First argument is a list of items to sort, second - optional function to use for sorting items in the list. Nothing new here by now, really.

Third argument, called p, keeps track of number of passes made on the list (see article on bubble sort on wikipedia.org for more on bubble sort passes ). I used argument instead of a static class variable to implement recursion in this case. P is set on the basis of length of the first argument automatically and is not supposed to be changed at any time by the user (Just another little twist here ;)).


/* Class: RecursiveSort - recursive sort algorithms container
   Author : Sylwester Wojnowski
   WWW : wojnowski.net.pl
    
   Methods: 
     public static bubble($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{
  public static function bubble($list,$compare = false,$p = 0){
    $n = count($list);
    $tmp = null;
    $i = 0;
    
    if(!$compare){
      $compare = function($a,$b){ return $a > $b; };
    }
     
    if( $n < 2 ) { return $list;}
    
    $p = $p === 0 ? $n - 1 : $p - 1; 
    
    while( $i <= $p - 1 ){ 
      if($compare($list[$i],$list[$i+1])){
        $tmp = $list[$i];
        $list[$i] = $list[$i+1];
        $list[$i+1] = $tmp;
      }
      $i++;
    }
      
    if ( $p === 1 ){ return $list;}
       
    return self::bubble( $list,$compare,$p );
  }
}

Sorting items with RecursiveSort::bubble

RecursiveSort::bubble sorts numbers in ascending order by default. It uses built-in comparison function for this.

Sorting objects in ascending order:


RecursiveSort::bubble(array(9,-22,8,1,35,7,0))

Sorting objects in descending order:


RecursiveSort::bubble(array(9,-22,8,1,35,7,0),function($a,$b){return $a < $b;})

Sorting arrays in descending order:


RecursiveSort::bubble(
  array(
    array(4,2),
    array(3,5),
    array(5,2)
  ),
  function($a,$b){
    return array_sum($a) < array_sum($b);
  }
);

Sorting object in descending order:


$products = array(
  (object)array("price" => 200),
  (object)array("price" => 700),
  (object)array("price" => 100),
);
    
RecursiveSort::bubble(
  $products,
  function($a,$b){
    return $a -> price < $b -> price;
  }
);

Final thoughts

As mentioned above, due to its asymptotic inefficiency, bubble sort algorithm is usually one of the last choices for sorting large lists. Still, it is fun to play with when testing features of a programming language like PHP.

As for personal gains, learning of not being able to pass an anonymous function as argument to another function in PHP is my take-home from this sorting adventure.

In case you would like to know more about PHP sort, some time ago I wrote an article on sorting objects with it.

This post was updated on 06 Apr 2017 18:18:06

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, 2019 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. "Recursive bubble sort algorithm in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/recursive-bubble-sort-algorithm-in-php