int function Partition (Array A, int Lb, int Ub); begin select a pivot from A[Lb]...A[Ub]; reorder A[Lb]...A[Ub] such that: all values to the left of the pivot are <= pivot all values to the right of the pivot are >= pivot return pivot position; end; procedure QuickSort (Array A, int Lb, int Ub); begin if Lb < Ub then M = Partition (A, Lb, Ub); QuickSort (A, Lb, M - 1); QuickSort (A, M + 1, Ub); end; |
In Figure 2-4(a), the pivot selected is 3. Indices are run starting at both ends of the array. One index starts on the left and selects an element that is larger than the pivot, while another index starts on the right and selects an element that is smaller than the pivot. In this case, numbers 4 and 1 are selected. These elements are then exchanged, as is shown in Figure 2-4(b). This process repeats until all elements to the left of the pivot <= the pivot, and all elements to the right of the pivot are >= the pivot. QuickSort recursively sorts the two subarrays, resulting in the array shown in Figure 2-4(c).
To find a pivot value, Partition could simply select the first element (A[Lb]). All other values would be compared to the pivot value, and placed either to the left or right of the pivot as appropriate. However, there is one case that fails miserably. Suppose the array was originally in order. Partition would always select the lowest value as a pivot and split the array with one element in the left partition, and Ub - Lb elements in the other. Each recursive call to quicksort would only diminish the size of the array to be sorted by one. Therefore n recursive calls would be required to do the sort, resulting in a O(n^{2}) run time. One solution to this problem is to randomly select an item as a pivot. This would make it extremely unlikely that worst-case behavior would occur.
count | time (µs) | stacksize | ||
---|---|---|---|---|
before | after | before | after | |
16 | 103 | 51 | 540 | 28 |
256 | 1,630 | 911 | 912 | 112 |
4,096 | 34,183 | 20,016 | 1,908 | 168 |
65,536 | 658,003 | 460,737 | 2,436 | 252 |