Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 33
Текст из файла (страница 33)
The analysis of the running time depends on the stable sort used as theintermediate sorting algorithm. When each digit is in the range 0 to k-1 (so that it can take onk possible values), and k is not too large, counting sort is the obvious choice. Each pass over nd-digit numbers then takes time Θ(n + k). There are d passes, so the total time for radix sort isΘ(d(n + k)).When d is constant and k = O(n), radix sort runs in linear time.
More generally, we have someflexibility in how to break each key into digits.Lemma 8.4Given n b-bit numbers and any positive integer r ≤ b, RADIX-SORT correctly sorts thesenumbers in Θ((b/r)(n + 2r)) time.Proof For a value r ≤ b, we view each key as having d = ⌈b/r⌉ digits of r bits each. Each digitis an integer in the range 0 to 2r - 1, so that we can use counting sort with k = 2r - 1. (Forexample, we can view a 32-bit word as having 4 8-bit digits, so that b = 32, r = 8, k = 2r - 1 =255, and d = b/r = 4.) Each pass of counting sort takes time Θ(n + k) = Θ(n + 2r) and there ared passes, for a total running time of Θ(d(n + 2r )) = Θ((b/r)(n + 2r)).For given values of n and b, we wish to choose the value of r, with r ≤ b, that minimizes theexpression (b/r)(n + 2r).
If b < ⌊lg n⌋, then for any value of r b, we have that (n + 2r) = Θ(n).Thus, choosing r = b yields a running time of (b/b)(n + 2b) = Θ(n), which is asymptoticallyoptimal. If b ≥ ⌊lg n⌋, then choosing r = ⌊lg n⌋ gives the best time to within a constant factor,which we can see as follows. Choosing r = ⌊lg n⌋ yields a running time of Θ(bn/ lg n). As weincrease r above ⌊lg n⌋, the 2r term in the numerator increases faster than the r term in thedenominator, and so increasing r above ⌊lg n⌋ yields a running time of Θ(bn/ lg n).
If insteadwe were to decrease r below ⌊lg n⌋, then the b/r term increases and the n + 2r term remains atΘ(n).Is radix sort preferable to a comparison-based sorting algorithm, such as quick-sort? If b =O(lg n), as is often the case, and we choose r ≈ lg n, then radix sort's running time is Θ(n),which appears to be better than quicksort's average-case time of Θ(n lg n). The constantfactors hidden in the Θ-notation differ, however. Although radix sort may make fewer passesthan quicksort over the n keys, each pass of radix sort may take significantly longer. Whichsorting algorithm is preferable depends on the characteristics of the implementations, of theunderlying machine (e.g., quicksort often uses hardware caches more effectively than radixsort), and of the input data.
Moreover, the version of radix sort that uses counting sort as theintermediate stable sort does not sort in place, which many of the Θ(n lg n)-time comparisonsorts do. Thus, when primary memory storage is at a premium, an in-place algorithm such asquicksort may be preferable.Exercises 8.3-1Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list ofEnglish words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG,BIG, TEA, NOW, FOX.Exercises 8.3-2Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, andquicksort? Give a simple scheme that makes any sorting algorithm stable. How muchadditional time and space does your scheme entail?Exercises 8.3-3Use induction to prove that radix sort works. Where does your proof need the assumption thatthe intermediate sort is stable?Exercises 8.3-4Show how to sort n integers in the range 0 to n2 - 1 in O(n) time.Exercises 8.3-5: ⋆In the first card-sorting algorithm in this section, exactly how many sorting passes are neededto sort d-digit decimal numbers in the worst case? How many piles of cards would an operatorneed to keep track of in the worst case?8.4 Bucket sortBucket sort runs in linear time when the input is drawn from a uniform distribution.
Likecounting sort, bucket sort is fast because it assumes something about the input. Whereascounting sort assumes that the input consists of integers in a small range, bucket sort assumesthat the input is generated by a random process that distributes elements uniformly over theinterval [0, 1). (See Section C.2 for a definition of uniform distribution.)The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, orbuckets, and then distribute the n input numbers into the buckets. Since the inputs areuniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket.
Toproduce the output, we simply sort the numbers in each bucket and then go through thebuckets in order, listing the elements in each.Our code for bucket sort assumes that the input is an n-element array A and that each elementA[i] in the array satisfies 0 ≤ A[i] < 1. The code requires an auxiliary array B[0 n - 1] oflinked lists (buckets) and assumes that there is a mechanism for maintaining such lists.(Section 10.2 describes how to implement basic operations on linked lists.)BUCKET-SORT(A)1 n ← length[A]2 for i ← 1 to n3456do insert A[i] into list B[⌊n A[i]⌋]for i ← 0 to n - 1do sort list B[i] with insertion sortconcatenate the lists B[0], B[1], .
. ., B[n - 1] together in orderFigure 8.4 shows the operation of bucket sort on an input array of 10 numbers.Figure 8.4: The operation of BUCKET-SORT. (a) The input array A[1 10]. (b) The arrayB[0 9] of sorted lists (buckets) after line 5 of the algorithm. Bucket i holds values in thehalf-open interval [i/10, (i + 1)/10). The sorted output consists of a concatenation in order ofthe lists B[0], B[1], . . ., B[9].To see that this algorithm works, consider two elements A[i] and A[j]. Assume without loss ofgenerality that A[i] ≤ A[j].
Since ⌊n A[i]⌋ ⌊n A[j]⌋, element A[i] is placed either into the samebucket as A[j] or into a bucket with a lower index. If A[i] and A[j] are placed into the samebucket, then the for loop of lines 4-5 puts them into the proper order. If A[i] and A[j] areplaced into different buckets, then line 6 puts them into the proper order. Therefore, bucketsort works correctly.To analyze the running time, observe that all lines except line 5 take O(n) time in the worstcase.
It remains to balance the total time taken by the n calls to insertion sort in line 5.To analyze the cost of the calls to insertion sort, let ni be the random variable denoting thenumber of elements placed in bucket B[i]. Since insertion sort runs in quadratic time (seeSection 2.2), the running time of bucket sort isTaking expectations of both sides and using linearity of expectation, we have(8.1)We claim that(8.2)for i = 0, 1, .
. ., n - 1. It is no surprise that each bucket i has the same value of, since eachvalue in the input array A is equally likely to fall in any bucket. To prove equation (8.2), wedefine indicator random variablesXij = I{A[j] falls in bucket i}for i = 0, 1, . . ., n - 1 and j = 1, 2, . . ., n. Thus,To compute, we expand the square and regroup terms:(8.3)where the last line follows by linearity of expectation. We evaluate the two summationsseparately. Indicator random variable Xij is 1 with probability 1/n and 0 otherwise, andthereforeWhen k ≠ j, the variables Xij and Xik are independent, and henceSubstituting these two expected values in equation (8.3), we obtainwhich proves equation (8.2).Using this expected value in equation (8.1), we conclude that the expected time for bucketsort is Θ(n) + n · O(2 - 1/n) = Θ(n).
Thus, the entire bucket sort algorithm runs in linearexpected time.Even if the input is not drawn from a uniform distribution, bucket sort may still run in lineartime. As long as the input has the property that the sum of the squares of the bucket sizes islinear in the total number of elements, equation (8.1) tells us that bucket sort will run in lineartime.Exercises 8.4-1Using Figure 8.4 as a model, illustrate the operation of BUCKET-SORT on the array A =.79, .13, .16, .64, .39, .20, .89, .53, .71, .42 .Exercises 8.4-2What is the worst-case running time for the bucket-sort algorithm? What simple change to thealgorithm preserves its linear expected running time and makes its worst-case running timeO(n lg n)?Exercises 8.4-3Let X be a random variable that is equal to the number of heads in two flips of a fair coin.What is E [X2]? What is E2 [X]?Exercises 8.4-4: ⋆for i = 1, 2, .
. ., n.We are given n points in the unit circle, pi = (xi, yi), such thatSuppose that the points are uniformly distributed; that is, the probability of finding a point inany region of the circle is proportional to the area of that region. Design a Θ(n) expected-timealgorithm to sort the n points by their distancesfrom the origin. (Hint: Design thebucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unitcircle.)Exercises 8.4-5: ⋆A probability distribution function P(x) for a random variable X is defined by P(x) = Pr {X ≤x}. Suppose that a list of n random variables X1, X2, .
. .,Xn is drawn from a continuousprobability distribution function P that is computable in O(1) time. Show how to sort thesenumbers in linear expected time.Problems 8-1: Average-case lower bounds on comparison sortingIn this problem, we prove an Ω(n lg n) lower bound on the expected running time of anydeterministic or randomized comparison sort on n distinct input elements. We begin byexamining a deterministic comparison sort A with decision tree TA. We assume that everypermutation of A's inputs is equally likely.a. Suppose that each leaf of TA is labeled with the probability that it is reached given arandom input. Prove that exactly n! leaves are labeled 1/n! and that the rest are labeled0.b. Let D(T) denote the external path length of a decision tree T ; that is, D(T) is the sumof the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and letLT and RT be the left and right subtrees of T.
Show that D(T) = D(LT) + D(RT) + k.c. Let d(k) be the minimum value of D(T) over all decision trees T with k > 1 leaves.Show that d(k) = min≤i≤k-1 {d(i) + d(k - i) + k}. (Hint: Consider a decision tree T with kleaves that achieves the minimum. Let i0 be the number of leaves in LT and k - i0 thenumber of leaves in RT.)d. Prove that for a given value of k > 1 and i in the range 1 ≤ i k - 1, the function i lg i +(k - i) lg(k - i) is minimized at i = k/2. Conclude that d(k) = Θ(k lg k).e. Prove that D(TA) = Θ(n! lg(n!)), and conclude that the expected time to sort n elementsis Θ(n lg n).Now, consider a randomized comparison sort B. We can extend the decision-tree model tohandle randomization by incorporating two kinds of nodes: ordinary comparison nodes and"randomization" nodes. A randomization node models a random choice of the formRANDOM(1, r) made by algorithm B; the node has r children, each of which is equally likelyto be chosen during an execution of the algorithm.f.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
