Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 34
Текст из файла (страница 34)
Show that for any randomized comparison sort B, there exists a deterministiccomparison sort A that makes no more comparisons on the average than B does.Problems 8-2: Sorting in place in linear timeSuppose that we have an array of n data records to sort and that the key of each record has thevalue 0 or 1. An algorithm for sorting such a set of records might possess some subset of thefollowing three desirable characteristics:1. The algorithm runs in O(n) time.2.
The algorithm is stable.3. The algorithm sorts in place, using no more than a constant amount of storage space inaddition to the original array.a. Give an algorithm that satisfies criteria 1 and 2 above.b. Give an algorithm that satisfies criteria 1 and 3 above.c. Give an algorithm that satisfies criteria 2 and 3 above.d. Can any of your sorting algorithms from parts (a)-(c) be used to sort n records with bbit keys using radix sort in O(bn) time? Explain how or why not.e. Suppose that the n records have keys in the range from 1 to k.
Show how to modifycounting sort so that the records can be sorted in place in O(n + k) time. You may useO(k) storage outside the input array. Is your algorithm stable? (Hint: How would youdo it for k = 3?)Problems 8-3: Sorting variable-length itemsa. You are given an array of integers, where different integers may have differentnumbers of digits, but the total number of digits over all the integers in the array is n.Show how to sort the array in O(n) time.b. You are given an array of strings, where different strings may have different numbersof characters, but the total number of characters over all the strings is n.
Show how tosort the strings in O(n) time.(Note that the desired order here is the standard alphabetical order; for example, a < ab< b.)Problems 8-4: Water jugsSuppose that you are given n red and n blue water jugs, all of different shapes and sizes. Allred jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug,there is a blue jug that holds the same amount of water, and vice versa.It is your task to find a grouping of the jugs into pairs of red and blue jugs that hold the sameamount of water.
To do so, you may perform the following operation: pick a pair of jugs inwhich one is red and one is blue, fill the red jug with water, and then pour the water into theblue jug. This operation will tell you whether the red or the blue jug can hold more water, or ifthey are of the same volume. Assume that such a comparison takes one time unit.
Your goal isto find an algorithm that makes a minimum number of comparisons to determine thegrouping. Remember that you may not directly compare two red jugs or two blue jugs.a. Describe a deterministic algorithm that uses Θ(n2) comparisons to group the jugs intopairs.b. Prove a lower bound of Θ(n lg n) for the number of comparisons an algorithm solvingthis problem must make.c. Give a randomized algorithm whose expected number of comparisons is O(n lg n),and prove that this bound is correct. What is the worst-case number of comparisons foryour algorithm?Problems 8-5: Average sortingSuppose that, instead of sorting an array, we just require that the elements increase onaverage.
More precisely, we call an n-element array A k-sorted if, for all i = 1, 2, . . ., n - k, thefollowing holds:a. What does it mean for an array to be 1-sorted?b. Give a permutation of the numbers 1, 2, . . ., 10 that is 2-sorted, but not sorted.c. Prove that an n-element array is k-sorted if and only if A[i] ≤ A[i + k] for all i = 1, 2, . .., n - k.d. Give an algorithm that k-sorts an n-element array in O(n lg(n/k)) time.We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.e.
Show that a k-sorted array of length n can be sorted in O(n lg k) time. (Hint: Use thesolution to Exercise 6.5-8.)f. Show that when k is a constant, it requires Θ(n lg n) time to k-sort an n-element array.(Hint: Use the solution to the previous part along with the lower bound on comparisonsorts.)Problems 8-6: Lower bound on merging sorted listsThe problem of merging two sorted lists arises frequently. It is used as a subroutine ofMERGE-SORT, and the procedure to merge two sorted lists is given as MERGE in Section2.3.1.
In this problem, we will show that there is a lower bound of 2n - 1 on the worst-casenumber of comparisons required to merge two sorted lists, each containing n items.First we will show a lower bound of 2n - o(n) comparisons by using a decision tree.a. Show that, given 2n numbers, there are possible ways to divide them into two sortedlists, each with n numbers.b. Using a decision tree, show that any algorithm that correctly merges two sorted listsuses at least 2n - o(n) comparisons.Now we will show a slightly tighter 2n - 1 bound.c. Show that if two elements are consecutive in the sorted order and from opposite lists,then they must be compared.d. Use your answer to the previous part to show a lower bound of 2n - 1 comparisons formerging two sorted lists.Chapter notesThe decision-tree model for studying comparison sorts was introduced by Ford and Johnson[94].
Knuth's comprehensive treatise on sorting [185] covers many variations on the sortingproblem, including the information-theoretic lower bound on the complexity of sorting givenhere. Lower bounds for sorting using generalizations of the decision-tree model were studiedcomprehensively by Ben-Or [36].Knuth credits H. H. Seward with inventing counting sort in 1954, and also with the idea ofcombining counting sort with radix sort. Radix sorting starting with the least significant digitappears to be a folk algorithm widely used by operators of mechanical card-sorting machines.According to Knuth, the first published reference to the method is a 1929 document by L. J.Comrie describing punched-card equipment.
Bucket sorting has been in use since 1956, whenthe basic idea was proposed by E. J. Isaac and R. C. Singleton.Munro and Raman [229] give a stable sorting algorithm that performs O(n1+ ) comparisons inthe worst case, where 0 < ≤ 1 is any fixed constant. Although any of the O(n lg n)-timealgorithms make fewer comparisons, the algorithm by Munro and Raman moves data onlyO(n) times and operates in place.The case of sorting n b-bit integers in o(n lg n) time has been considered by many researchers.Several positive results have been obtained, each under slightly different assumptions aboutthe model of computation and the restrictions placed on the algorithm. All the results assumethat the computer memory is divided into addressable b-bit words.
Fredman and Willard [99]introduced the fusion tree data structure and used it to sort n integers in O(n lg n/ lg lg n) time.time by Andersson [16]. These algorithms requireThis bound was later improved tothe use of multiplication and several precomputed constants. Andersson, Hagerup, Nilsson,and Raman [17] have shown how to sort n integers in O(n lg lg n) time without usingmultiplication, but their method requires storage that can be unbounded in terms of n.
Usingmultiplicative hashing, one can reduce the storage needed to O(n), but the O(n lg lg n) worstcase bound on the running time becomes an expected-time bound. Generalizing theexponential search trees of Andersson [16], Thorup [297] gave an O(n(lg lg n)2)-time sortingalgorithm that does not use multiplication or randomization, and uses linear space.
Combiningthese techniques with some new ideas, Han [137] improved the bound for sorting to O(n lg lgn lg lg lg n) time. Although these algorithms are important theoretical breakthroughs, they areall fairly complicated and at the present time seem unlikely to compete with existing sortingalgorithms in practice.Chapter 9: Medians and Order StatisticsOverviewThe ith order statistic of a set of n elements is the ith smallest element. For example, theminimum of a set of elements is the first order statistic (i = 1), and the maximum is the nthorder statistic (i = n).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
