Quick Sort

// Complete the quickSort function below.
function quickSort($arr) {
    $size = sizeof($arr);
    quickSort2($arr, 0, $size - 1);    
}
function quickSort2($arr, $left, $right) {
    if ($left >= $right) {
        return;
    }    
    $pivot = $arr[($right + $left)/2];
    $index = partition($arr, $left, $right, $pivot);
    quickSort2($arr, $left, $index);
    quickSort2($arr, $index + 1, $right);
}

function partition($arr, $left, $right, $pivot) {    
    while ($left <= $right) {
        while ($arr[$left] < $pivot) {
        $left++;
        }

        while ($arr[$right] > $pivot) {
            $right--;
        }

        if ($left <= $right) {
            $temp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $arr[$left];
            $left++;
            $right--;
        }
    }
    return $left;
}

Leave a Reply