S1.5 ANALY S IS O F ALGO R IT H MS 21 the algorithm itself,not any particular program.For quicksort,three natural quantities are involved: A-the number of partitioning stages B-the number of exchanges C-the number of compares On a typical computer,the total running time of quicksort might be expressed with a formula,such as 4C+11B+35A. (2) The exact values of these coefficients depend on the machine language pro- gram produced by the compiler as well as the properties of the machine being used;the values given above are typical.Such expressions are quite useful in comparing different algorithms implemented on the same machine.Indeed, the reason that quicksort is of practical interest even though mergesort is"op- timal"is that the cost per compare(the coefficient of C)is likely to be sig- nificantly lower for quicksort than for mergesort,which leads to significantly shorter running times in typical practical applications. Theorem 1.3 (Quicksort analysis).Quicksort uses,on the average, (N-1)/2 partitioning stages, 2(N 1)(HN+1-3/2)2NInN 1.846N compares,and (N+1)(HN+1-3)/3+1.333NInN -.865N exchanges to sort an array of N randomly ordered distinct elements. Proof.The exact answers here are expressed in terms of the harmonic numbers Hw=∑1/k, 1≤k≤N the first of many well-known"special"number sequences that we will encoun- ter in the analysis of algorithms. As with mergesort,the analysis of quicksort involves defining and solv- ing recurrence relations that mirror directly the recursive nature of the al- gorithm.But,in this case,the recurrences must be based on probabilistic www.it-ebooks.info
§Ș.Ȝ A Ś ō Ř ť ş ŕ ş ś Œ A Ř œ ś Ş ŕ Š Ŕ ř ş șȘ the algorithm itself, not any particular program. For quicksort, three natural quantities are involved: A – the number of partitioning stages B – the number of exchanges C – the number of compares On a typical computer, the total running time of quicksort might be expressed with a formula, such as 4C + 11B + 35A. (2) Ļe exact values of these coefficients depend on the machine language program produced by the compiler as well as the properties of the machine being used; the values given above are typical. Such expressions are quite useful in comparing different algorithms implemented on the same machine. Indeed, the reason that quicksort is of practical interest even though mergesort is “optimal” is that the cost per compare (the coefficient of C) is likely to be signiŀcantly lower for quicksort than for mergesort, which leads to signiŀcantly shorter running times in typical practical applications. Ļeorem 1.3 (Quicksort analysis). Quicksort uses, on the average, (N − 1)/2 partitioning stages, 2(N + 1) (HN+1 − 3/2) ≈ 2NlnN − 1.846N compares, and (N + 1) (HN+1 − 3) /3 + 1 ≈ .333NlnN − .865N exchanges to sort an array of N randomly ordered distinct elements. Proof. Ļe exact answers here are expressed in terms of the harmonic numbers HN = ∑ 1≤k≤N 1/k, the ŀrst of many well-known “special” number sequences that we will encounter in the analysis of algorithms. As with mergesort, the analysis of quicksort involves deŀning and solving recurrence relations that mirror directly the recursive nature of the algorithm. But, in this case, the recurrences must be based on probabilistic www.it-ebooks.info
22 CHAPTER ONE SI.5 statements about the inputs.If CN is the average number of compares to sort N elements,we have Co =C1=0 and Cx=N+1+,C-1+Cx-》 for N>1. (3) 1≤j≤N To get the total average number of compares,we add the number of compares for the first partitioning stage(N+1)to the number of compares used for the subarrays after partitioning.When the partitioning element is the jth largest (which occurs with probability 1/N for each 1 <j<N),the subarrays after partitioning are of size j-1 and N-j. Now the analysis has been reduced to a mathematical problem(3)that does not depend on properties of the program or the algorithm.This recur- rence relation is somewhat more complicated than(1)because the right-hand side depends directly on the history of all the previous values,not just a few. Still,(3)is not difficult to solve:first change j to N-j+1 in the second part of the sum to get Cw=N+1+,∑C-1 2 for N>0. 1≤j<N Then multiply by N and subtract the same formula for N-1 to eliminate the sum: NCN-(N-1)CN-1=2N +2CN-1 for N>1. Now rearrange terms to get a simple recurrence NCN =(N+1)CN-1+2N for N>1. This can be solved by dividing both sides by N(N+1): CNC+ 2 for N>1. N+1 N Iterating,we are left with the sum Cw-G+2∑，k N+12 3≤k≤N+1 www.it-ebooks.info
șș C Ŕ ō Ŝ Š ő Ş O Ś ő §Ș.Ȝ statements about the inputs. If CN is the average number of compares to sort N elements, we have C0 = C1 = 0 and CN = N + 1 + 1 N ∑ 1≤j≤N (Cj−1 + CN−j ), for N > 1. (3) To get the total average number of compares, we add the number of compares for the ŀrst partitioning stage (N +1) to the number of compares used for the subarrays after partitioning. When the partitioning element is the jth largest (which occurs with probability 1/N for each 1 ≤ j ≤ N), the subarrays after partitioning are of size j − 1 and N − j. Now the analysis has been reduced to a mathematical problem (3) that does not depend on properties of the program or the algorithm. Ļis recurrence relation is somewhat more complicated than (1) because the right-hand side depends directly on the history of all the previous values, not just a few. Still, (3) is not difficult to solve: ŀrst change j to N − j + 1 in the second part of the sum to get CN = N + 1 + 2 N ∑ 1≤j≤N Cj−1 for N > 0. Ļen multiply by N and subtract the same formula for N −1 to eliminate the sum: NCN − (N − 1)CN−1 = 2N + 2CN−1 for N > 1. Now rearrange terms to get a simple recurrence NCN = (N + 1)CN−1 + 2N for N > 1. Ļis can be solved by dividing both sides by N(N + 1): CN N + 1 = CN−1 N + 2 N + 1 for N > 1. Iterating, we are left with the sum CN N + 1 = C1 2 + 2 ∑ 3≤k≤N+1 1/k www.it-ebooks.info
S1.5 ANALY SIS O F ALGORITHMS 23 which completes the proof,since C1=0. As implemented earlier,every element is used for partitioning exactly once,so the number of stages is always N;the average number of exchanges can be found from these results by first calculating the average number of exchanges on the first partitioning stage. The stated approximations follow from the well-known approximation to the harmonic number HNInN +.57721....We consider such ap- proximations below and in detail in Chapter 4. Exercise 1.12 Give the recurrence for the total number of compares used by quicksort on all N!permutations of N elements. Exercise 1.13 Prove that the subarrays left after partitioning a random permutation are themselves both random permutations.Then prove that this is not the case if,for example,the right pointer is initialized atj:=+1for partitioning. Exercise 1.14 Follow through the steps above to solve the recurrence Aw=1+员4 for N>0. 1≤j≤N 2,118,000 Gray dot:one experiment Black dot:mean for 100 experiments 2NInN 2W1nW-1.846N 166,000 12,000 1,00010,000 100,000 Problem size (length of array to be sorted) Figure 1.1 Quicksort compare counts:empirical and analytic www.it-ebooks.info
§Ș.Ȝ A Ś ō Ř ť ş ŕ ş ś Œ A Ř œ ś Ş ŕ Š Ŕ ř ş șȚ which completes the proof, since C1 = 0. As implemented earlier, every element is used for partitioning exactly once, so the number of stages is always N; the average number of exchanges can be found from these results by ŀrst calculating the average number of exchanges on the ŀrst partitioning stage. Ļe stated approximations follow from the well-known approximation to the harmonic number HN ≈ lnN + .57721 · · · . We consider such approximations below and in detail in Chapter 4. Exercise 1.12 Give the recurrence for the total number of compares used by quicksort on all N! permutations of N elements. Exercise 1.13 Prove that the subarrays left after partitioning a random permutation are themselves both random permutations. Ļen prove that this is not the case if, for example, the right pointer is initialized at j:=r+1 for partitioning. Exercise 1.14 Follow through the steps above to solve the recurrence AN = 1 + 2 N ∑ 1≤j≤N Aj−1 for N > 0. 2,118,000 2N lnN Gray dot: one experiment Black dot: mean for 100 experiments 2N lnN – 1.846N 166,000 12,000 1,000 Problem size (length of array to be sorted) Cost (quicksort compares) 10,000 100,000 Figure 1.1 Quicksort compare counts: empirical and analytic www.it-ebooks.info
24 CHAPTER ONE SI.5 Exercise 1.15 Show that the average number of exchanges used during the first par- titioning stage (before the pointers cross)is(N-2)/6.(Thus,by linearity of the recurrences,BN =CN-AN.) Figure 1.1 shows how the analytic result of Theorem 1.3 compares to empirical results computed by generating random inputs to the program and counting the compares used.The empirical results(100 trials for each value of N shown)are depicted with a gray dot for each experiment and a black dot at the mean for each N.The analytic result is a smooth curve fitting the formula given in Theorem 1.3.As expected,the fit is extremely good. Theorem 1.3 and(2)imply,for example,that quicksort should take about 11.667NInN-.601N steps to sort a random permutation of N el- ements for the particular machine described previously,and similar formulae for other machines can be derived through an investigation of the properties of the machine as in the discussion preceding(2)and Theorem 1.3.Such formu- lae can be used to predict(with great accuracy)the running time of quicksort on a particular machine.More important,they can be used to evaluate and compare variations of the algorithm and provide a quantitative testimony to their effectiveness. Secure in the knowledge that machine dependencies can be handled with suitable attention to detail,we will generally concentrate on analyzing generic algorithm-dependent quantities,such as"compares"and"exchanges,' in this book.Not only does this keep our focus on major techniques of anal- ysis,but it also can extend the applicability of the results.For example,a slightly broader characterization of the sorting problem is to consider the items to be sorted as records containing other information besides the sort key,so that accessing a record might be much more expensive(depending on the size of the record)than doing a compare(depending on the relative size of records and keys).Then we know from Theorem 1.3 that quicksort com- pares keys about 2NInN times and moves records about.667NIn N times, and we can compute more precise estimates of costs or compare with other algorithms as appropriate. Quicksort can be improved in several ways to make it the sorting method of choice in many computing environments.We can even analyze compli- cated improved versions and derive expressions for the average running time that match closely observed empirical times [29].Of course,the more intri- cate and complicated the proposed improvement,the more intricate and com- www.it-ebooks.info
șț C Ŕ ō Ŝ Š ő Ş O Ś ő §Ș.Ȝ Exercise 1.15 Show that the average number of exchanges used during the ŀrst partitioning stage (before the pointers cross) is (N − 2)/6. (Ļus, by linearity of the recurrences, BN = 1 6CN − 1 2AN .) Figure 1.1 shows how the analytic result of Ļeorem 1.3 compares to empirical results computed by generating random inputs to the program and counting the compares used. Ļe empirical results (100 trials for each value of N shown) are depicted with a gray dot for each experiment and a black dot at the mean for each N. Ļe analytic result is a smooth curve ŀtting the formula given in Ļeorem 1.3. As expected, the ŀt is extremely good. Ļeorem 1.3 and (2) imply, for example, that quicksort should take about 11.667NlnN − .601N steps to sort a random permutation of N elements for the particular machine described previously, and similar formulae for other machines can be derived through an investigation of the properties of the machine as in the discussion preceding (2) and Ļeorem 1.3. Such formulae can be used to predict (with great accuracy) the running time of quicksort on a particular machine. More important, they can be used to evaluate and compare variations of the algorithm and provide a quantitative testimony to their effectiveness. Secure in the knowledge that machine dependencies can be handled with suitable attention to detail, we will generally concentrate on analyzing generic algorithm-dependent quantities, such as “compares” and “exchanges,” in this book. Not only does this keep our focus on major techniques of analysis, but it also can extend the applicability of the results. For example, a slightly broader characterization of the sorting problem is to consider the items to be sorted as records containing other information besides the sort key, so that accessing a record might be much more expensive (depending on the size of the record) than doing a compare (depending on the relative size of records and keys). Ļen we know from Ļeorem 1.3 that quicksort compares keys about 2NlnN times and moves records about .667NlnN times, and we can compute more precise estimates of costs or compare with other algorithms as appropriate. Quicksort can be improved in several ways to make it the sorting method of choice in many computing environments. We can even analyze complicated improved versions and derive expressions for the average running time that match closely observed empirical times [29]. Of course, the more intricate and complicated the proposed improvement, the more intricate and comwww.it-ebooks.info
S1.5 ANALY SIS O F ALGO R IT H M S 25 plicated the analysis.Some improvements can be handled by extending the argument given previously,but others require more powerful analytic tools. Small subarrays.The simplest variant of quicksort is based on the observation that it is not very efficient for very small files(for example,a file of size 2 can be sorted with one compare and possibly one exchange),so that a simpler method should be used for smaller subarrays.The following exercises show how the earlier analysis can be extended to study a hybrid algorithm where "insertion sort"(see $7.6)is used for files of size less than M.Then,this analysis can be used to help choose the best value of the parameter M. Exercise 1.16 How many subarrays of size 2 or less are encountered,on the average, when sorting a random file of size N with quicksort? Exercise 1.17 If we change the first line in the quicksort implementation above to if r-1<=M then insertionsort(1,r)else (see $7.6),then the total number of compares to sort N elements is described by the recurrence for N>M; CN N+1+N,∑.(C-1+C-) 1≤j≤N N(N-1) forN≤M. Solve this exactly as in the proof of Theorem 1.3. Exercise 1.18 Ignoring small terms(those significantly less than N)in the answer to the previous exercise,find a function f(M)so that the number of compares is approximately 2NInN +f(M)N. Plot the function f(M),and find the value of M that minimizes the function. Exercise 1.19 As M gets larger,the number of compares increases again from the minimum just derived.How large must M get before the number of compares ex- ceeds the original number(at M=0)? Median-of-three quicksort.A natural improvement to quicksort is to use sampling:estimate a partitioning element more likely to be near the middle of the file by taking a small sample,then using the median of the sample.For example,if we use just three elements for the sample,then the average number www.it-ebooks.info
§Ș.Ȝ A Ś ō Ř ť ş ŕ ş ś Œ A Ř œ ś Ş ŕ Š Ŕ ř ş șȜ plicated the analysis. Some improvements can be handled by extending the argument given previously, but others require more powerful analytic tools. Small subarrays. Ļe simplest variant of quicksort is based on the observation that it is not very efficient for very small ŀles (for example, a ŀle of size 2 can be sorted with one compare and possibly one exchange), so that a simpler method should be used for smaller subarrays. Ļe following exercises show how the earlier analysis can be extended to study a hybrid algorithm where “insertion sort” (see §7.6) is used for ŀles of size less than M. Ļen, this analysis can be used to help choose the best value of the parameter M. Exercise 1.16 How many subarrays of size 2 or less are encountered, on the average, when sorting a random ŀle of size N with quicksort? Exercise 1.17 If we change the ŀrst line in the quicksort implementation above to if r-l<=M then insertionsort(l,r) else (see §7.6), then the total number of compares to sort N elements is described by the recurrence CN = N + 1 + 1 N ∑ 1≤j≤N (Cj−1 + CN−j ) for N > M; 1 4N(N − 1) for N ≤ M. Solve this exactly as in the proof of Ļeorem 1.3. Exercise 1.18 Ignoring small terms (those signiŀcantly less than N) in the answer to the previous exercise, ŀnd a function f(M) so that the number of compares is approximately 2NlnN + f(M)N. Plot the function f(M), and ŀnd the value of M that minimizes the function. Exercise 1.19 As M gets larger, the number of compares increases again from the minimum just derived. How large must M get before the number of compares exceeds the original number (at M = 0)? Median-of-three quicksort. A natural improvement to quicksort is to use sampling: estimate a partitioning element more likely to be near the middle of the ŀle by taking a small sample, then using the median of the sample. For example, if we use just three elements for the sample, then the average number www.it-ebooks.info