Quicksort uses a subroutine known as partition
that picks one element p in the array to use as a pivot and then partially rearranges the elements in the array such that all elements smaller than or equal to the pivot are to the left of the pivot, and all larger elements are to the right of the pivot. After a single partitioning step, the algorithm recursively sorts the sub-arrays to the left and right of the pivot.
We first outline this partitioning step
partition(A, start, finish): Input: an array A and integer indices start and finish denoting a sub-array of A. Output: returns the index of the pivot element and partitions A such that all items less than or equal to the pivot are to the left of the pivot, and all items greater than the pivot are to the right. /* choose a pivot element by selecting the last element in the sub-array A[start..finish] (inclusive) */ pivot = A[finish] left = start right = finish-1 while left <= right if A[left] <= pivot //small items don't need to move right left++ elif A[right] > pivot //big items don't need to move left right-- else //swap a big item on the left with a small item on the right swap(A, left, right) //move the pivot to the right spot swap(A, left, finish) return left //return index of final pivot location
With partition as a building block, we can define a recursive function quicksort that sorts a sub-array A[left..right].
quickSort(A, left, right): Input: an array A and integer indices left and right denoting a sub-array of A. Output: Returns nothing, but modifies the elements in A[left..right] so they are sorted in ascending order. if right > left idx = partition(A, left, right) quickSort(A, left, idx-1) quickSort(A, idx+1, right)Usually, we think of a sort function as simply taking an array and its size as input. We can write a version of quickSort with this prototype as well using a small wrapper.
qsort(A, n): Input: an array A of n elements Output: Nothing, but array A is sorted in ascending order after the function call quickSort(A, 0, n-1)