3
\$\begingroup\$

Does this code show proper implementation of quick sort algorithm? If not, why? Can this code further be improved?

<?php

$unsorted = range(1,20);
shuffle($unsorted);

function quick_sort($array)
{
    // find array size
    $length = count($array);

    // base case test, if array of length 0 then just return array
    if($length <= 1){

        return $array;
    }
    else{

        // select random element as pivot
        $rand = rand(0,$length-1);
        $pivot = $array[$rand];

        // create two partitions
        $left = $right = array();

        // place elements around pivot by comparison
        for($i = 0; $i < count($array); $i++)
        {
            if($i==$rand)continue;

            if($array[$i] < $pivot){
                $left[] = $array[$i];
            }
            else{
                $right[] = $array[$i];
            }
        }

        // recurse
        return array_merge(quick_sort($left), array($pivot), quick_sort($right));
    }
}
echo '<pre>';
print_r($unsorted);
print_r(quick_sort($unsorted));

?>
\$\endgroup\$
2
\$\begingroup\$

The else statement for array length check is superfluous. Also, your pivot choosing policy has a flaw: on already sorted array it will degrade to quadratic running time; I suggest you choose the pivot randomly or choose the pivot from several elements.

You don't need to do that array creation stuff you seem to do: quicksort can be implemented in-place.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.