PHP Program for Quick Sort Algorithm Example

A PHP program for quick sort uses a recursive function that picks a pivot, partitions the array into smaller and larger elements, and sorts them with quickSort() function. Example: function quickSort(array $arr): array { if(count($arr) < 2) return $arr; $pivot = $arr[0]; $left = $right = []; for($i=1; $i

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort an array with quick sort, pick one element as a pivot. Then split the array into two parts: elements smaller than the pivot and elements larger or equal. Sort these parts by repeating the same steps. Finally, join the sorted parts and the pivot to get a sorted array.

Algorithm

1

Check if the array has less than two elements; if yes, return it as is.

2

Choose the first element as the pivot.

3

Create two empty arrays: one for elements smaller than the pivot, one for larger or equal.

4

Loop through the rest of the array, placing each element into the smaller or larger array.

5

Recursively quick sort the smaller and larger arrays.

6

Combine the sorted smaller array, pivot, and sorted larger array and return the result.

Code

php

<?php
function quickSort(array $arr): array {
    if(count($arr) < 2) return $arr;
    $pivot = $arr[0];
    $left = $right = [];
    for($i = 1; $i < count($arr); $i++) {
        if($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

$input = [10, 7, 8, 9, 1, 5];
$output = quickSort($input);
print_r($output);

Output

Array
(
    [0] => 1
    [1] => 5
    [2] => 7
    [3] => 8
    [4] => 9
    [5] => 10
)

Dry Run

Let's trace the array [10, 7, 8, 9, 1, 5] through the quickSort function.

1

Initial call

Array is [10, 7, 8, 9, 1, 5]. Pivot is 10. Left and right arrays start empty.

2

Partitioning

Elements less than 10 go to left: [7, 8, 9, 1, 5]. No elements go to right.

3

Recursive call on left

Call quickSort on [7, 8, 9, 1, 5]. Pivot is 7.

4

Partitioning left subarray

Left: [1, 5], Right: [8, 9]

5

Recursive calls on subarrays

quickSort([1, 5]) returns [1, 5], quickSort([8, 9]) returns [8, 9]

6

Combine left subarrays

Combine [1, 5], pivot 7, and [8, 9] to get [1, 5, 7, 8, 9]

7

Combine all

Combine sorted left [1, 5, 7, 8, 9], pivot 10, and empty right to get [1, 5, 7, 8, 9, 10]

Step	Pivot	Left Array	Right Array	Result
1	10	[7,8,9,1,5]	[]	Recursive calls on left
2	7	[1,5]	[8,9]	Combine subarrays
3	1	[]	[5]	[1,5] sorted
4	8	[]	[9]	[8,9] sorted
5	-	-	-	[1,5,7,8,9,10] final

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into smaller and larger parts, helping to sort by comparison.

Step 2: Partitioning

Elements are split into two groups based on comparison with the pivot using < operator.

Step 3: Recursion

The function calls itself on smaller parts to sort them, then combines results for the full sorted array.

Alternative Approaches

In-place Quick Sort

php

<?php
function quickSortInPlace(array &$arr, int $low, int $high) {
    if ($low < $high) {
        $pi = partition($arr, $low, $high);
        quickSortInPlace($arr, $low, $pi - 1);
        quickSortInPlace($arr, $pi + 1, $high);
    }
}

function partition(array &$arr, int $low, int $high): int {
    $pivot = $arr[$high];
    $i = $low - 1;
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }
    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    return $i + 1;
}

$arr = [10, 7, 8, 9, 1, 5];
quickSortInPlace($arr, 0, count($arr) - 1);
print_r($arr);

This method sorts the array without extra memory by swapping elements in place, which is more memory efficient but slightly more complex.

Using PHP built-in sort

php

<?php
$arr = [10, 7, 8, 9, 1, 5];
sort($arr);
print_r($arr);

Using PHP's built-in <code>sort()</code> is the simplest and fastest for most cases but does not teach the quick sort algorithm.

Complexity: O(n log n) average, O(n^2) worst case time, O(log n) average due to recursion stack, O(n) worst case space

Time Complexity

Quick sort divides the array and sorts parts recursively. Average time is O(n log n) because it splits roughly in half each time. Worst case is O(n^2) when pivot choices are poor, like always smallest or largest element.

Space Complexity

The recursive calls use stack space proportional to the depth of recursion, which is O(log n) on average. The simple version uses extra arrays, increasing space to O(n). In-place quick sort reduces extra space.

Which Approach is Fastest?

In-place quick sort is fastest and most memory efficient for large arrays. The simple recursive version is easier to understand but uses more memory. PHP's built-in sort is optimized and fastest for practical use.

Approach	Time	Space	Best For
Simple Recursive Quick Sort	O(n log n) average	O(n)	Learning and small arrays
In-place Quick Sort	O(n log n) average	O(log n)	Large arrays with memory constraints
PHP Built-in sort()	O(n log n)	O(1)	Practical sorting needs