Quick Sort Algorithm in PHP

Quick Sort is the most widely used sorting algorithm. It is official sorting algorithm in PHP (sort). It has average case runtime O(n log n) and worst case O(n^2). If you want to understand how Quick Sort works, jump to bottom of the page to see a quick video. 

function quickSort(array $arr) : array
{
    $low = 0;
    $high = count($arr) - 1;

    partition($arr, $low, $high);

    return $arr;
}

function partition(&$arr, int $left, int $right) : void
{
    $pivotLocation = arrange($arr, $left, $right);

    if ($left < $pivotLocation - 1) { // sort left half
        partition($arr, $left, $pivotLocation-1);

    }

    if ($pivotLocation < $right) { // sort right half
        partition($arr, $pivotLocation, $right);
    }
}

function arrange(&$arr, $left, $right) : int
{
    $pivot = $arr[ ($left + $right) / 2 ];

    while ($left <= $right) {

        while($arr[$left] < $pivot) ++$left; // find element on left that should on right

        while($arr[$right] > $pivot) --$right; // find element on right that should be on left

        if ($left <= $right) {
            $temp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $temp;

            ++$left;
            --$right;
        }
    }

    return $left;
}

Source Code of Algorithm Series: https://github.com/EresDev/Algorithms

Leave a Reply

avatar
  Subscribe  
Notify of