Everyone knows that Quicksort is much more performant than Bubble Sort. That on average, Bubble Sort is an O(n^2) algorithm and Quicksort is an O(n log n) algorithm. That Quicksort is much faster. I wanted to test this out, though. With extremely low number sets, maybe Bubble Sort is the way to go? How about with extremely large number sets? Will the deep recursion of Quicksort blow up my machine? I figured that Quicksort would always be the clear winner, but sometimes there are extreme cases when an underdog algorithm is better. But anyways, I was mostly interested in seeing just how much faster Quicksort is over Bubble Sort. At least in my development environment. With real numbers.

So I did some testing. To encourage fairness, each algorithm always had the same exact set to sort as the other. Here are my results:

Quicksort vs Bubble Sort data chart

Quicksort vs Bubble Sort line graph

Quicksort vs Bubble Sort line graph - time comparison

In short, I was very surprised to see that to sort 5,000 numbers, it took Bubble Sort almost 3 hours and Quicksort just 5.5 seconds. That's just insane, and is also why I stopped testing at this point.  I'd like to continue pushing Quicksort to see if it reaches a breaking point, but that will have to wait until next time.

The code to do this testing is available on my github, but here's a look at the two algorithms:

Bubble Sort:

<?php
namespace SortAlgorithm;

class BubbleSort
    implements ISort
{
    /**
     * @var array
     */
    private $_array;
    
    /**
     * Sorts array via Bubble Sort.
     * 
     * @param array $array
     * @return array
     */
    public function sort(array &$array = array())
    {
        $this->_array = &$array;
        
        if(count($this->_array) == 0) {
            return $this->_array;
        }
        
        $this->_bubbleSort();
    }
    
    /**
     * Keeps swapping the lowest numbers to the left until there
     * are no swaps.
     * 
     * @param void
     * @return void
     */
    private function _bubbleSort()
    {
        $did_swap = true;
        
        // Keep swapping inversions until there have been
        // no swaps.
        while($did_swap) {
            
            //Reset the swap state.
            $did_swap = false;
            
            for($i = 0; $i < count($this->_array); $i++) {
                if($i != 0) {
                    if($this->_array[$i-1] > $this->_array[$i]) {
                        
                        //Swap the inversion.
                        $temp = $this->_array[$i-1];
                        $this->_array[$i-1] = $this->_array[$i];
                        $this->_array[$i] = $temp;
                        
                        $did_swap = true;
                    }
                }
            }
        }
    }
    
}

Quicksort:

<?php
namespace SortAlgorithm;

class QuickSort
    implements ISort
{
    /**
     * @var array
     */
    private $_array;

    /**
     * Sorts array via Quick Sort.
     *
     * @param array $array
     * @return void
     */
    public function sort(array &$array = array())
    {
        $this->_array = &$array;

        if(count($this->_array) == 0) {
            return $this->_array;
        }

        $this->_quickSort(0, count($this->_array)-1);
    }

    /**
     * Sort a partition of the array, moving smallest numbers left of the
     * pivot point and largest numbers to the right of the pivot point.
     *
     * @param int $left
     * @param int $right
     * @return boolean
     */
    private function _quickSort($left, $right)
    {
        if($this->_isSorted($left, $right)) {
            return true;
        }

        $i = $left;
        $j = $right;
        $pivot = $this->_array[floor(($left + $right) / 2)];

        while ($i <= $j) {

            //Keep moving from the left.
            while ($this->_array[$i] < $pivot) {
                $i++;
            }

            //Keep moving from the right.
            while ($this->_array[$j] > $pivot) {
                $j--;
            }

            //Need to swap.
            if($i <= $j) {
                $tmp = $this->_array[$i];
                $this->_array[$i] = $this->_array[$j];
                $this->_array[$j] = $tmp;
                $i++;
                $j--;
            }
        };

        if ($left < $j) {
            $this->_quickSort($left, $j);
        }

        if ($i < $right) {
            $this->_quickSort($i, $right);
        }

        return true;
    }

    /**
     * Check if the current array is sorted, given
     * it's left and right index.
     *
     * @param int $left
     * @param int $right
     * @return boolean
     */
    private function _isSorted($left, $right)
    {
        for($i = $left; $i < $right; $i++) {
            if($this->_array[$i] > $this->_array[$i + 1]) {
                return false;
            }
        }

        return true;
    }
}