Quick-sort

Quick-sort algorithm and its partitioning technique

Quick-sort is another recursive sorting algorithm, discovered by Tony Hoare in 1959 and first published in 1961. In this algorithm, the hard part is splitting the array into smaller subarrays before recursion so that merging the sorted subarrays is trivial. It follows these steps:

1. Choose a pivot element from the array.
2. Partition the array into three subarrays respectively containing the elements smaller than the pivot, the pivot element itself, and the elements larger than the pivot.
3. Recursively quick-sort the first and last subarrays.

A more detailed pseudocode is given below. In the $Partition$ subroutine, the input parameter $p$ is the index of the pivot element in the unsorted array; the subroutine partitions the array and returns the new index of the pivot element. There are many different efficient partitioning algorithms; the one presented here is attributed to Nico Lomuto. The variable $l$ counts the number of items in the array that are less than the pivot element.

$\underline{QuickSort(A[1 .. n]):} \\ \hspace{0.4cm} if\space n > 1 \\ \hspace{1cm} Choose\space a\space pivot\space element\space A[p] \\ \hspace{1cm} r ← Partition(A, p) \\ \hspace{1cm} QuickSort(A[1 .. r − 1]) \space{\color{Red} 〈〈Recurse!〉〉} \\ \hspace{1cm} QuickSort(A[r+1..n]) \space {\color{Red} 〈〈Recurse!〉〉}$ ...