PHP 7 Data Structures and Algorithms

Understanding quick sort

Quick sort is another efficient sorting algorithm that applies the divide-and-conquer method. Although it does not divide into equal halves like merge sort, it creates dynamic partitions to sort the data. This is how quick sort works:

1. Pick a random value from the array, which we will call pivot.
2. Reorder the array so that the item that is smaller than the pivot goes to the left of it, and the items that are greater than, or equal to, the pivot go to the right of it. This is known as partitioning.
3. Recursively call steps 1 and 2 to solve the two subarrays (left and right of pivot) until all items are sorted.

There are many ways to picking a pivot from the array. We can either choose the left-most item of the array ...