Building quicksort with php

Question

I recently read about quicksort and was wondering whether it would be smart to build my own function to sort things with quicksort or if it would be inefficent. What do you think is the built in sort function better than a selfbuilt quicksort function?

Answer 1

From http://php.net/sort

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

The core PHP functions will be implemented in c, rather than PHP, so they should generally be significantly faster than anything you can write yourself in PHP. There will be cases where it is faster to write your own, but I guess these would be when you have a very specific case and you can make your own specific optimisations for that. I think that is unlikely to be the case here.

Answer 2

In fact I did this for a data point on a presentation I am putting together. The test sorts an array of 250,000 integers using the native sort function and an implementation of the quicksort algorithm written in php. The contents of the array are exactly the same for both runs, the data is randomized, and the time reported is only for performing the sort, not other processing necessary to invoke the php interpreter.

Results:

  Native sort implementation:  1.379 seconds
PHP quicksort implementation: 30.615 seconds

Definitely use the native implementation. That should be the case for any interpreted language.

The results for the other languages I tested with the same conditions using the same implementation on the same hardware and OS, provide an interesting performance comparison and put the PHP result in perspective:

               C: 0.107 seconds
            Java: 0.250 seconds
JavaScript (FF3): 4.401 seconds

Notably, Chrome and Safari performed much faster for the JavaScript test, but I don't include those here because those tests were recorded in a different environment.

Answer 3

Stick with the built-in sort function. Quicksort is a simple algorithm, but to get good performance on computers that are actually in use requires a little bit of finesse. It is more than likely that the built-in function is already more optimized than anything you would write in a reasonable amount of time. (The constant-factor speedup from being written in C instead of PHP is also probably helpful.)

If you are sorting so many elements that you are slowed down by the sort function, you are probably doing something wrong. (This is PHP after all. You should use a general-purpose language for data-intensive processing. It will be easier to write your code, and it will run faster.)

Answer 4

For reference there is a PHP implementation here:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#PHP

Answer 5

One thing about the php quick sort (asort, arsort, etc) is that they mess your equal values, that is to say that values with different keys will randomly swap position, even between different runs. Amazing that code can produce a different order using the same data again and again. In the end I had to implement my own quick sort to remove this anomaly.

Answer 6

Just for fun, here is an in-place version of quicksort in PHP I came up with. The trick here is to pass the array to be sorted as a reference.

function partition(&$arr,$leftIndex,$rightIndex)
{
    $pivot=$arr[($leftIndex+$rightIndex)/2];

    while ($leftIndex <= $rightIndex) 
    {        
        while ($arr[$leftIndex] < $pivot)             
                $leftIndex++;
        while ($arr[$rightIndex] > $pivot)
                $rightIndex--;
        if ($leftIndex <= $rightIndex) {  
                $tmp = $arr[$leftIndex];
                $arr[$leftIndex] = $arr[$rightIndex];
                $arr[$rightIndex] = $tmp;
                $leftIndex++;
                $rightIndex--;
        }
    }
    return $leftIndex;
}

function quickSort(&$arr, $leftIndex, $rightIndex)
{
    $index = partition($arr,$leftIndex,$rightIndex);
    if ($leftIndex < $index - 1)
        quickSort($arr, $leftIndex, $index - 1);
    if ($index < $rightIndex)
        quickSort($arr, $index, $rightIndex);
}

Answer 7

Please find below the class to implement the Quick Sort in PHP -

            <?php
            class quickSort{
            /* low  --> Starting index,  high  --> Ending index */
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }
                public function qsort($low,$high){
                    if($low===null || $high===null){    
                        return false;
                    }
                    if($low < $high){           
                        $pi = $this->partition($low,$high);
                        $this->qsort($low,$pi-1); /*before pivot*/
                        $this->qsort($pi+1,$high); /*before pivot*/
                    }
                }

                /* This function takes last element as pivot, places
                   the pivot element at its correct position in sorted
                    array, and places all smaller (smaller than pivot)
                   to left of pivot and all greater elements to right
                   of pivot */
                public function partition($low,$high){
                    if($low===null || $high===null){
                        return false;
                    }
                    $pivot = $this->arr[$high];
                    $i = $low-1; /*index of smaller element*/

                    for($j = $low; $j <= $high-1; $j++)
                    {
                        // If current element is smaller than or equal to pivot

                        if($this->arr[$j] <= $pivot)
                        {
                            $i++;    // increment index of smaller element
                            $this->swap($i,$j);         
                        }
                    }
                    //swap arr[i + 1] and arr[high])
                    $this->swap($i+1,$high);

                    return $i+1;    
                }

                public function swap($i,$j){
                    $p=$this->arr[$i];
                    $q=$this->arr[$j];
                    $this->arr[$i]=$q;
                    $this->arr[$j]=$p;      
                }
            }
            $arr = array(10, 80, 30, 90, 40, 50, 70);
            $obj = new quickSort($arr);
            $obj->qsort(0,6);
            print_r($obj->arr);


            ?>