The Algorithm

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.

1. If the size of the array is zero or one, then return the array. This is the base case.
2. Select an element from the array to be used as the pivot element. This is the pivot selection step.
3. Create two new arrays. Place all the elements from the original array that are less than the pivot element into one of these sub-arrays and all the elements that are greater than the pivot element into the other sub-array. This is the partitioning step.
4. Return the array that contains the result of the quicksorted sub-array that contains the elements less than the pivot, followed by the pivot, followed by the result of the quicksorted sub-array that contains the elements greater than the pivot. This is the recursive divide step.

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