Everything about Quick Sort Algorithm and its implementation in PHP

QuickSort is a highly efficient, comparison-based sorting algorithm that follows the divide-and-conquer strategy to sort an array or a list of elements. It was developed by Tony Hoare in 1960. The key idea behind QuickSort is to select a pivot element from the array, partition the other elements into two sub-arrays based on the pivot, and then recursively sort these sub-arrays.

Here’s a step-by-step explanation of the QuickSort algorithm:

1. 1. Choose a Pivot: Select an element from the array to serve as the pivot. The choice of pivot can affect the algorithm’s performance. In the basic implementation, the first element is often chosen as the pivot.
   2. Partitioning: Rearrange the elements in the array such that all elements less than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. The pivot itself is in its final sorted position. This step is performed using a process called partitioning.
      • Initialize two pointers, left and right, at the two ends of the array.
      • Move the left pointer towards the right until an element greater than the pivot is found.
      • Move the right pointer towards the left until an element less than the pivot is found.
      • If left is still to the left of right, swap the elements at left and right.
      • Repeat the above two steps until left is no longer to the left of right.
      • Finally, swap the pivot element with the element at the right pointer.
   3. Recursion: After the partitioning step, the pivot is in its final sorted position. Recursively apply the QuickSort algorithm to the sub-arrays on the left and right of the pivot.
   4. Base Case: The recursion stops when the sub-arrays have one or zero elements, as they are already sorted by definition.
   5. Combine Sub-Arrays: Since the pivot and sub-arrays are sorted, combining the left sub-array, pivot, and right sub-array will result in a fully sorted array.

Here’s a high-level pseudocode of the QuickSort algorithm:

procedure quickSort(array)
    if length(array) <= 1
        return array
    pivot = choosePivot(array)
    left = []
    right = []
    for element in array (excluding pivot)
        if element < pivot
            add element to left
        else
            add element to right
    sortedLeft = quickSort(left)
    sortedRight = quickSort(right)
    return concatenate(sortedLeft, pivot, sortedRight)
end procedure

QuickSort has an average-case time complexity of O(n log n), where n is the number of elements to be sorted. The worst-case time complexity is O(n^2), which occurs when the pivot selection consistently results in unbalanced partitions. However, in practice, QuickSort often outperforms other sorting algorithms due to its low constant factors and efficient cache utilization.

To improve QuickSort’s worst-case behavior, variations like Randomized QuickSort, which randomly select the pivot, and Three-Way QuickSort, which handles duplicate elements efficiently, have been proposed.

PHP Implementation of Quick Sort

Follow this video for complete guidance :

function quickSort($array) {
    $length = count($array);
    
    if ($length <= 1) {
        return $array;
    }
    
    $pivot = $array[0];
    $left = $right = array();

    for ($i = 1; $i < $length; $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

    return array_merge(quickSort($left), array($pivot), quickSort($right));
}

$unsortedArray = array(7, 2, 1, 6, 8, 5, 3, 4);
$sortedArray = quickSort($unsortedArray);

echo "Unsorted Array: " . implode(", ", $unsortedArray) . "<br>";
echo "Sorted Array: " . implode(", ", $sortedArray);