• Data Structure and Algorithm - Quick Sort
  • Problem to Solve
  • Pseudocode
  • PHP Implementation
  • The End

#Data Structure and Algorithm - Quick Sort

In this tutorial, we will learn a simple sorting algorithm - Quick Sort.

#Problem to Solve

Given a list of numbers as shown below, please sort them in ascending order.

$numbers = [21,25,100,98,89,77];

Requirements:

• You are required to use Quick Sort algorithm when sorting the numbers.
• You are required to implement the algorithm in PHP language.

#Pseudocode

Quick Sort is also a divide and conquer algorithm, similar to Merge Sort. It works by choosing an element(pivot) from the list and placing elements that are less than the pivot on its left side and elements that are greater than the pivot on its right side. We repeat the steps for both left side and right side until the list can no longer be divided.

Choosing a pivot can be tricky, normally we just use the first or the last element.

Pseudocode of Quick Sort algorithm can be written as follows:

PROCEDURE function quickSort
    IF list is empty
        Return the list
    END IF
 
    Choose first element as the pivot
 
    FOR each element of the list start from position 1
 
        IF element is greater than pivot
            Assign it to the left side
        ELSE
            Assign it to the right side
        END IF
 
    END FOR
 
    return quickSort(left)+pivot+quickSort(right)
 
END PROCEDURE

#PHP Implementation

As we can see, we are using recursion for this algorithm. Typically, a divide and conquer algorithm implies the algorithm can be written recursively.

<?php
$arrayToSort = [21, 25, 100, 98, 89, 77];
 
function quickSort($data)
{
    if (count($data) == 0) {
        return $data;
    }
 
    $pivot = $data[0];
 
    $left = $right = [];
 
    for ($i = 1; $i < count($data); $i++) {
        if ($data[$i] < $pivot) {
            $left[] = $data[$i];
        } else {
            $right[] = $data[$i];
        }
    }
 
    return array_merge(quicksort($left), array($pivot), quicksort($right));
}
 
print_r(quickSort($arrayToSort));
 
// Output:
/*
Array
(
    [0] => 21
    [1] => 25
    [2] => 77
    [3] => 89
    [4] => 98
    [5] => 100
)
*/

Quick Sort is indeed very simple to implement as a divide and conquer algorithm.

#The End

If you like our post, please follow us on Twitter and help spread the word. We need your support to continue. If you have questions or find our mistakes in above tutorial, do leave a comment below to let us know.