Quick Sort Program in Php

Quicksort is a divide and conquer algorithm.

This Sorting algorithm that picks an element (“the pivot”) and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted.

Algorithm Steps

1. Pick an element from the array, this element is called as pivot element.
2. Divide the unsorted array of elements in two arrays with values less than the pivot come in the first sub array.
3. while all elements with values greater than the pivot come in the second sub-array (equal values can go either way).
4. This step is called the partition operation.
5. Recursively repeat the step 2(until the sub-arrays are sorted) to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Algorithm
partition(Array, low, high) is
pivot = A[high]
i = low
for j = low to high – 1 do
if A[j] ≤ pivot then
swap A[i] with A[j]
i = i + 1
swap A[i] with A[high]
return i

Program

//Swap Function
function swap(&$array,$left,$right) {
    $temp = $array[$right]; 
    $array[$right] = $array[$left];
    $array[$left] = $temp;         
}
//Quick Sort Function
function quicksort(&$array,$left,$right) {
    if($left < $right) { 
        $boundary = $left;
        for ($i = $left + 1; $i < $right; $i++) { 
            if ($array[$i] < $array[$left]) { 
                swap($array, $i, ++$boundary);
            }
        }
        swap($array,$left,$boundary);
        quicksort($array, $left, $boundary);
        quicksort($array, $boundary + 1, $right);
    }     
}
//Display Array
function display_array($array){
   $len = count($array);
   for($i=0;$i<$len;$i++){
      echo $array[$i];
      echo ($i==$len-1)? ".":",";
   }
}
$array  = [1,8,6,10,7,2,3,9,5]; 
$left = 0;
$right = count($array); 
display_array($array);
echo "<br>";
quicksort($array,$left,$right);
display_array($array);
// 1,8,6,10,7,2,3,9,5.
// 1,2,3,5,6,7,8,9,10