计算机算法导论-第8章.ppt

1、Introduction to Algorithms 计算机算法导论,20072008年第一学期,Sorting and Order Statistics,Introduction,Sorting problem,Definition: Input: A sequence of numbers. Output: A permutation , such that a1 a2 an .,The structure of the data,Definition: Record = key + satellite data Assumption: The input consists only of

2、 numbers,Why sorting?,The need inherent in an application Algorithms often use sorting as a key subroutine A wide variety of sorting algorithms, a rich set of techniques A problem can be proved a nontrivial lower bound. Many engineering issues come to fore when implementing sorting algorithms.,Sorti

3、ng algorithms,A in-place sorting algorithm Comparison sort The counting sort algorithm The radix sort algorithm The bucket sort algorithm,Order statistics,The ith order statistic of a set of n numbers is the ith smallest number in the set.,8、 Sorting in linear time,8.1 Lower bounds for sorting,Assum

4、ption: All of the input elements are distinct All comparisons have the form ai aj,How fast can we sort?,All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements. E.g.,insertion sort, merge sort, quicksort, heapsort. The bes

5、t worst-case running time that weve seen for comparison sorting is O(n lg n) . Is O(n lg n) the best we can do? Decision trees can help us answer this question.,Decision-tree model,A decision tree can model the execution of any comparison sort: One tree for each input size n. View the algorithm as s

6、plitting whenever it compares two elements. The tree contains the comparisons along all possible instruction traces. The running time of the algorithm = the length of the path taken. Worst-case running time = height of tree.,Lower bound for decision-tree sorting,Lower bound for comparison sorting,Co

7、rollary. Heapsort and merge sort are asymptotically optimal comparison sorting algorithms.,8.2 Counting sort,Sorting in linear time Counting sort: No comparisons between elements. Input: A1 . . n, where A j1, 2, , k . Output: B1 . . n, sorted. Auxiliary storage: C1 . . k .,Counting sort,for i 1 to k

8、 do Ci 0 for j 1 to n do CA j CA j + 1 Ci = |key = i| for i 2 to k do Ci Ci + Ci1 Ci = |key i| for j n downto 1 do BCA j A j CA j CA j 1,Running time,If k = O(n), then counting sort takes (n) time. But, sorting takes (n lg n) time! Wheres the fallacy? Answer: Comparison sorting takes (n lg n) time.

9、Counting sort is not a comparison sort. In fact, not a single comparison between elements occurs!,8.3 Radix sort, Origin: Herman Holleriths card-sorting machine for the 1890 U.S. Census. (See Appendix .) Digit-by-digit sort. Holleriths original (bad) idea: sort on most-significant digit first. Good idea: Sort on least-significant digit first with auxiliary stable sort.,8.4 Bucket so