PHP Searching and Sorting Algorithm: Quick sort

Last update on December 20 2024 10:21:41 (UTC/GMT +8 hours)

Write a PHP program to sort a list of elements using Quick sort.

Quick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.

Visual presentation - Quick Sort algorithm :

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.

Animation credits : RolandH

Sample Solution:

PHP Code:

<?php
// Function to perform Quick Sort algorithm
function quick_sort($my_array)
{
    // Base case: if array has 0 or 1 elements, it's already sorted
    $length = count($my_array);
    if ($length <= 1) {
        return $my_array;
    }

    // Select pivot element (here, we choose the middle element)
    $pivot_key = (int)($length / 2);
    $pivot = $my_array[$pivot_key];

    // Partition the array into elements less than pivot and elements greater than pivot
    $left = $right = array();
    foreach ($my_array as $key => $value) {
        if ($key == $pivot_key) {
            continue;
        }
        if ($value <= $pivot) {
            $left[] = $value;
        } else {
            $right[] = $value;
        }
    }

    // Recursively sort the partitions
    return array_merge(
        quick_sort($left),
        array($pivot), // Pivot element
        quick_sort($right)
    );
}

$my_array = array(3, 0, 2, 5, -1, 4, 1);
echo 'Original Array : ' . implode(',', $my_array) . "\n";
$my_array = quick_sort($my_array);
echo 'Sorted Array : ' . implode(',', $my_array);
?>

Output:

Original Array : 3,0,2,5,-1,4,1
Sorted Array : -1,0,1,2,3,4,5

Explanation:

In the exercise above,

• The "quick_sort()" function takes an array '$my_array' as input and returns the sorted array.
• If the array has 0 or 1 element, it's considered already sorted, so the function returns the array as is.
• Otherwise, the function selects a pivot element from the array. In this implementation, the pivot is chosen as the middle element.
• The function then partitions the array into two sub-arrays: elements less than or equal to the pivot ($left) and elements greater than the pivot ($right).
• Recursively, the quick sort algorithm is applied to the left and right sub-arrays.
• Finally, the sorted sub-arrays are merged along with the pivot element to produce the sorted array.
• The original array is sorted using this function, and the sorted array is printed out.

This algorithm has an average time complexity of O(n log n) and is efficient for sorting large datasets.

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: PHP Searching and Sorting Algorithm Exercises Home.
Next: Write a PHP program to sort a list of elements using Heap sort.