计算机算法导论-第8章课件

1、计算机算法导论_第8章课件计算机算法导论_第8章课件Sorting and Order StatisticsIntroductionSorting and Order StatisticsInSorting problemDefinition:Input: A sequence of numbers.Output: A permutation , such that a1 a2 an .Sorting problemDefinition:The structure of the dataDefinition:Record = key + satellite dataAssumption:The

2、 input consists only of numbersThe structure of the dataDefinWhy sorting?The need inherent in an applicationAlgorithms often use sorting as a key subroutineA wide variety of sorting algorithms, a rich set of techniquesA problem can be proved a nontrivial lower bound.Many engineering issues come to f

3、ore when implementing sorting algorithms. Why sorting?The need inherent Sorting algorithmsA in-place sorting algorithmComparison sortThe counting sort algorithmThe radix sort algorithmThe bucket sort algorithmSorting algorithmsA in-place sOrder statisticsThe ith order statistic of a set of n numbers

4、 is the ith smallest number in the set.Order statisticsThe ith order 8、 Sorting in linear time8、 Sorting in linear time8.1 Lower bounds for sortingAssumption:All of the input elements are distinctAll comparisons have the form ai aj 8.1 Lower bounds for sortingAsHow fast can we sort?All the sorting a

5、lgorithms 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 tree

6、s can help us answer this question.How fast can we sort?All the s计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件Decision-tree modelA 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 tw

7、o 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.Decision-tree modelA decision Lower bound for decision-tree sortingLower bound for decision-tree Lower bound

8、 for comparison sortingCorollary. Heapsort and merge sort are asymptotically optimal comparison sorting algorithms.Lower bound for comparison sor8.2 Counting sortSorting in linear timeCounting sort: No comparisons between elements. Input: A1 . . n, where A j1, 2, , k . Output: B1 . . n, sorted. Auxi

9、liary storage: C1 . . k .8.2 Counting sortSorting in liCounting sortfor i 1 to k do Ci 0for 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 1Counting sortfor i 1 to k计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8

10、章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件Running timeIf 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)

11、 time. Counting sort is not a comparison sort. In fact, not a single comparison between elements occurs!Running timeIf k = O(n), then 计算机算法导论_第8章课件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) i

12、dea: sort on most-significant digit first. Good idea: Sort on least-significant digit first with auxiliary stable sort.8.3 Radix sort Origin: Herma计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件计算机算法导论_第8章课件8.4 Bucket sortAssumption:The input is drawn from a uniform distr