## 2.4 Quicksort (Partition Exchange Sort) Next we look at a sorting algorithm, called "Quicksort," that was developed by Hoare (1962). Quicksort is similar to Mergesort in that the sort is accomplished by dividing the array into two partitions and then sorting each partition recursively. In Quicksort, however, the array is partitioned by placing all items smaller than some pivot item before that item and all items larger than the pivot item after it. The pivot item can be any item, and for convenience we will simply make it the first one. The following example illustrates how Quicksort works. Example 2.3****Suppose the array contains these numbers in sequence:  1. Partition the array so that all items smaller than the pivot item are to the left of it and all items larger are to the right:  2. Sort the subarrays  **** After the partitioning, the order of the items in the subarrays is unspecified and is a result of how the partitioning is implemented. We have ordered them according to how the partitioning routine, which will be presented shortly, would place them. The important thing is that all items smaller than the pivot item are to the left of it, and all items larger are to the right of it. Quicksort is then called recursively to sort each of the two subarrays. They are partitioned, and this procedure is continued until an array with one item is reached. Such an array is trivially sorted. Example 2.3 shows the solution at the problem-solving level. [Figure 2.3](#ch02fig03) illustrates the steps done by a human when sorting with Quicksort. The algorithm follows. [](fig2-3_0.jpg) Figure 2.3: The steps done by a human when sorting with Quicksort. The subarrays are enclosed in rectangles whereas the pivot points are free. Algorithm 2.6: Quicksort****Problem: Sort *n* keys in nondecreasing order. Inputs: positive integer *n*, array of keys *S* indexed from 1 to *n.* Outputs: the array *S* containing the keys in nondecreasing order. ``` void quicksort (index low, index high) { index pivotpoint; if (high > low){ partition(low, high, pivotpoint); quicksort(low, pivotpoint - 1); quicksort(pivotpoint + 1, high); } } ``` **** Following our usual convention, *n* and *S* are not parameters to procedure *quicksort.* If the algorithm were implemented by defining *S* globally and *n* was the number of items in *S*, the top-level call to *quicksort* would be as follows: *quicksort*(1, *n*); The partitioning of the array is done by procedure *partition.* Next we show an algorithm for this procedure. Algorithm 2.7: Partition****Problem: Partition the array *S* for Quicksort. Inputs: two indices, *low* and *high*, and the subarray of *S* indexed from *low* to *high.* Outputs: *pivotpoint*, the pivot point for the subarray indexed from *low* to *high.* ``` void partition (index low, index high, index& pivotpoint) { index i, j; keytype pivotitem; pivotitem = S[low]; // Choose first item for j = low; //pivotitem. for (i = low + 1; i <= high; i++) if (S[i] < pivotitem){ j++; exchange S[i] and S[j]; } pivotpoint = j; exchange S[low] and S[pivotpoint]; // Put pivotitem at pivotpoint. } ``` **** Procedure *partition* works by checking each item in the array in sequence. Whenever an item is found to be less than the pivot item, it is moved to the left side of the array. [Table 2.2](#ch02table02) shows how *partition* would proceed on the array in Example 2.3. Table 2.2: An example of procedure *partition*\[[\*](#ftn.ch02fnt02)\]*i* *j* *S*\[1\] *S*\[2\] *S*\[3\] *S*\[4\] *S*\[5\] *S*\[6\] *S*\[7\] *S*\[8\] — — 15 22 13 27 12 10 20 25 ← Initial values 2 1 **15** **22** 13 27 12 10 20 25 3 2 **15** 22 **13** 27 12 10 20 25 4 2 **15** 13 22 **27** 12 10 20 25 5 3 **15** 13 22 27 **12** 10 20 25 6 4 **15** 13 12 27 22 **10** 20 25 7 4 **15** 13 12 10 22 27 **20** 25 8 4 **15** 13 12 10 22 27 20 **25** — 4 10 13 12 15 22 27 20 25 ← Final values \[[\*](#ch02fnt02)\]Items compared are in boldface. Items just exchanged appear in squares. Next we analyze Partition and Quicksort. ****Analysis of [Algorithm 2.7](#ch02ex13) Every-Case Time Complexity (Partition)Basic operation: the comparison of *S\[i\]* with *pivotitem.* Input size: *n* = *high* − *low* + 1, the number of items in the subarray. Because every item except the first is compared, *T*(*n*) = *n* − 1. We are using *n* here to represent the size of the subarray, not the size of the array *S.* It represents the size of *S* only when *partition* is called at the top level. **** Quicksort does not have an every-case complexity. We will do worst-case and average-case analyses. ****Analysis of [Algorithm 2.6](#ch02ex12) Worst-Case Time Complexity (Quicksort)Basic operation: the comparison of *S\[i\]* with *pivotitem* in *partition.* Input size: *n*, the number of items in the array *S.* Oddly enough, it turns out that the worst case occurs if the array is already sorted in nondecreasing order. The reason for this should become clear. If the array is already sorted in nondecreasing order, no items are less than the first item in the array, which is the pivot item. Therefore, when *partition* is called at the top level, no items are placed to the left of the pivot item, and the value of *pivotpoint* assigned by *partition* is 1. Similarly, in each recursive call, *pivotpoint* receives the value of *low.* Therefore, the array is repeatedly partitioned into an empty subarray on the left and a subarray with one less item on the right. For the class of instances that are already sorted in nondecreasing order, we have  We are using the notation *T(n)* because we are presently determining the every-case complexity for the class of instances that are already sorted in nondecreasing order. Because *T*(0) = 0, we have the recurrence  This recurrence is solved in Example B.16 in [Appendix B](LiB0102.html#1369). The solution is  We have established that the worst case is at least *n(n* − 1)/2. Although intuitively it may now seem that this is as bad as things can get, we still need to show this. We will accomplish this by using induction to show that, for all *n*,  Induction base: for *n* = 0  Induction hypothesis: Assume that, for 0 ≤ *k* < *n*,  Induction step: We need to show that  For a given *n*, there is some instance with size *n* for which the processing time is *W(n).* Let *p* be the value of *pivotpoint* returned by *partition* at the top level when this instance is processed. Because the time to process the instances of size *p* − 1 and *n* − *p* can be no more than *W(p* − 1) and *W(n* − *p*), respectively, we have  The last inequality is by the induction hypothesis. Algebraic manipulations can show that for 1 ≤ *p* ≤ *n* this last expression is  This completes the induction proof. We have shown that the worst-case time complexity is given by  **** The worst case occurs when the array is already sorted because we always choose the first item for the pivot item. Therefore, if we have reason to believe that the array is close to being sorted, this is not a good choice for the pivot item. When we discuss Quicksort further in [Chapter 7](LiB0052.html#627), we will investigate other methods for choosing the pivot item. If we use these methods, the worst case does not occur when the array is already sorted. But the worst-case time complexity is still *n(n* − 1)/2. In the worst case, [Algorithm 2.6](#ch02ex12) is no faster than Exchange Sort ([Algorithm 1.3](LiB0008.html#32)). Why then is this sort called Quicksort? As we shall see, it is in its average-case behavior that Quicksort earns its name. **** Analysis of [Algorithm 2.6](#ch02ex12) Average-Case Time Complexity (Quicksort)Basic operation: the comparison of *S\[i\]* with *pivotitem* in *partition* Input size: *n*, the number of items in the array *S.* We will assume that we have no reason to believe that the numbers in the array are in any particular order, and therefore that the value of *pivotpoint* returned by *partition* is equally likely to be any of the numbers from 1 through *n.* If there was reason to believe a different distribution, this analysis would not be applicable. The average obtained is, therefore, the average sorting time when every possible ordering is sorted the same number of times. In this case, the average-case time complexity is given by the following recurrence:  In the exercises we show that  Plugging this equality into [Equality 2.1](#ch02eqn01) yields  Multiplying by *n* we have  Applying [Equality 2.2](#ch02eqn02) to *n* − 1 gives  Subtracting [Equality 2.3](#ch02eqn03) from [Equality 2.2](#ch02eqn02) yields  which simplifies to  If we let  we have the recurrence  Like the recurrence in Example B.22 in [Appendix B](LiB0102.html#1369), the approximate solution to this recurrence is given by  which implies that  **** Quicksort's average-case time complexity is of the same order as Mergesort's time complexity. Mergesort and Quicksort are compared further in [Chapter 7](LiB0052.html#627) and in Knuth (1973).