Quicksort is a fast sorting algorithm that uses a divide-and-conquer problem solving approach. Unlike the basic sorting algorithms we have already examined, quicksort uses recursion. Given an array of elements to sort, the algorithm recursively divides the array into smaller and smaller arrays. Quicksort then sorts these very small arrays and combines the results to create a sorted version of the original array. Because of its recursive nature, the quicksort implementation can be hard to understand. Before examining an implementation, we consider the idea behind the algorithm.
The quicksort algorithm can be summarized in four basic steps. Presented in the context of sorting an array, these steps are as follows.
Stepping through an example illustrates how these four steps sort a set of data. Consider the array presented in Figure 1.
Figure 1 An unsorted array
Since the array in Figure 1 contains more than one element, quicksort enters step two and selects a pivot element. There are many different strategies we can use to pick this pivot element. One that is simple involves choosing the middle element of the array as the pivot element. This element contains the value 33. After selecting the pivot element, quicksort partitions the remaining elements into two sub-arrays. One sub-array contains the elements of the partitioned array whose values are less than 33, and the other sub-array contains the elements whose values are greater than 33. Figure 2 illustrates this first pivot and partition step. In this figure, a circle denotes the pivot element.
Figure 2 Pivot selection and partition
The first partition creates two smaller arrays. The quicksort algorithm then recursively calls itself on these arrays. Notice that both of these arrays contain two or more elements. Therefore, the algorithm selects pivot elements for each array and partitions their remaining elements into smaller arrays. The result of this appears in Figure 3.
Figure 3 Second level partitioning
The quicksort algorithm only needs to select pivot elements and partition sub-arrays that contain more than one element. From Figure 3, we see after two partitions we are left with four sub-arrays. These arrays appear in the bottom row of the figure. Starting from the left side of the figure, the first sub-array contains only one element (the value 3). The second sub-array contains elements 12 and 21, and the third sub-array contains elements 52 and 53. The fourth sub-array contains zero elements. The empty set sign (a circle with a diagonal line through it) denotes that this sub-array contains zero elements. The quicksort algorithm does not need to pivot and partition the first and fourth arrays since they each contain less than two elements. At this point, these two sub-arrays are sorted. Since the second and third arrays each contain more than one element, there is the possibility they are not in sorted order. Quicksort must recursively pivot and partition these arrays. This is demonstrated in Figure 4.
Figure 4 After last necessary partition
The recursive nature of quicksort breaks down the original array into smaller and smaller sub-arrays. The pivoting and partitioning of these sub-arrays eventually results in the sorting of the entire array. Figure 5 depicts the sorted version of the original array from our ongoing example.
Figure 5 The sorted array