Implementing quick sort

As shown in the pseudocode, we will have two functions to implement a quick sort: one function to do the quick sort itself, and the other for the partitioning. Here is the implementation to do the quick sort:

function quickSort(array &$arr, int $p, int $r) {
if($p < $r) {
$q = partition($arr, $p, $r);
quickSort($arr, $p, $q);
quickSort($arr, $q+1, $r);
}
}

Here is the implementation to do the partitioning:

function partition(array &$arr, int $p, int $r){ 
$pivot = $arr[$p];
$i = $p-1;
$j = $r+1;
while(true)
{
do {
$i++;
} while($arr[$i] < $pivot && $arr[$i] != $pivot);
do {
$j--;
} while($arr[$j] > $pivot && $arr[$j] != $pivot);

if($i < $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
} else {
return $j;
}
}
}

$arr = [20, 45, 93, 67, 10, 97, 52, 88, 33, 92];

quickSort($arr, 0, count($arr)-1);
echo implode(",", $arr);

If we visually illustrate the pivot and the sorting in the partitions, we can see the following image. For simplicity, we are only showing the steps where swapping took place:

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset