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

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 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.,Sorting 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,Assumption: 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 best 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 splitting 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,Corollary. 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 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. 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