PHP 7 Data Structures and Algorithms

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;  } ...