[ACCEPTED]-Building quicksort with php-quicksort

Accepted answer
Score: 27

From http://php.net/sort

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

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

Score: 16

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

Results:

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

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

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

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

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

Score: 5

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

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

Score: 4

For reference there is a PHP implementation 1 here:

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

Score: 2

Just for fun, here is an in-place version 3 of quicksort in PHP I came up with. The 2 trick here is to pass the array to be sorted 1 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);
}
Score: 1

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

Score: 0

Please find below the class to implement 1 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);


            ?>

More Related questions