Sorting Algorithms and Their Implementation in PHP

Welcome to the practice-based lesson dedicated to Simple Sorting Algorithms. Sorting is one of the most investigated classes of algorithms in computer science. Understanding different methods of sorting becomes more crucial as data size increases. In this lesson, we are going to revisit the basic sorting algorithms: Bubble, Selection, and Insertion sorts. These are not only excellent exercises for those new to coding, but they also lay the groundwork for more complex sorting algorithms like QuickSort.

Before we dive into the basics, let's peek into more complex territory by examining QuickSort, a popular divide-and-conquer sorting algorithm. The idea behind it is to pick a pivot element from the array and partition the other elements into two arrays according to whether they are less than or greater than the pivot. The pivot is then placed in its correct sorted position between the two subarrays. This process is recursively applied to each of the two arrays around the pivot, leading to a sorted array.

Here's how you can implement QuickSort in PHP:

<?php

function quickSort(&$arr, $low, $high) {
    if ($low < $high) {
        $pi = partition($arr, $low, $high);

        // Recursively sort elements before partition and after partition
        quickSort($arr, $low, $pi - 1);
        quickSort($arr, $pi + 1, $high);
    }
}

function partition(&$arr, $low, $high) {
    $pivot = $arr[$high];
    $i = $low - 1;

    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] <= $pivot) {
            $i++;
            // Swap $arr[$i] and $arr[$j]
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }

    // Swap $arr[$i + 1] and $arr[$high] (or pivot)
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;

    return $i + 1;
}

$arr = array(10, 7, 8, 9, 1, 5);
$n = count($arr);

quickSort($arr, 0, $n - 1);

echo "Sorted array: \n";
for ($i = 0; $i < $n; $i++) {
    echo $arr[$i] . " ";
}
// Output: 1 5 7 8 9 10

Here's a quick explanation of how the QuickSort algorithm works:

1. Recursive Function: quickSort(&$arr, $low, $high) sorts the array segment from $low to $high. The & signifies that the array is passed by reference.
2. Base Case: The sorting continues as long as $low < $high, ensuring the segment is valid.
3. Partitioning: The partition(&$arr, $low, $high) function selects the last element as pivot. It rearranges elements so that those less than or equal to the pivot are on the left. The pivot is then placed in its sorted position, and its index is returned.
4. Recursion: The array is recursively sorted by applying quickSort to the left (quickSort($arr, $low, $pi - 1)) and right (quickSort($arr, $pi + 1, $high)) segments around the pivot.
5. Result: The recursive division results in a fully sorted array. QuickSort uses this divide-and-conquer strategy to efficiently arrange data.