线性时间内排序剖析.ppt

Page ? * Tel : Email : lipinggao@usst.edu.cn Office: room 612（新图书馆楼602房间） Chp8 Sorting in Linear Time * Introduction Comparison sort: the sorted order an algorithm determine is based only on comparisons between the input elements Any comparison must take ?(n lg n) comparisons in the worst case Merge sort and heapsort are asymptotically optimal Sorting in linear time Of course, use operations other than comparisons to determine the sorted order Counting sort, radix sort, and bucket sort * The Decision-Tree Model Decision tree A full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size i:j ? compare a[i] and a[j] Each leaf is annotated by a permutation ?(1), ?(2), …, ?(n) n! possible permutations in total The execution of the sorting algorithm corresponds to tracing a path from the root to a leaf A necessary condition for a comparison sort to be correct is that each of the n! permutations on n elements must appear as one of the leaves of the decision tree, and that each of these leaves must be reachable from the root by a path (reachable leaves) corresponding to an actual execution of the comparison sort * The Decision-Tree Model 5 7 3 5 7 3 5 3 7 3 7 3 5 * A Lower Bound for the Worst Case The length of the longest path from the root of a decision tree to any of its reachable leaves represents the worst-case number of comparisons that the corresponding sorting algorithm performs Height of a decision tree Theorem 8.1. Any comparison sort algorithm requires ?(n lg n) comparisons in the worst case Consider a decision tree of height h with l reachable leaves n! ? l ? 2h h ? lg(n!) (since the lg function is monotonically increasing)= ?(n lg n) (by equation (3.18)) * Counting Sort * Counting Sort Overview Assumption: n input elements are integers in the range of 0 to k (integer). ?(n+k) ? When k=O(n), counting sort: ?(n) Basic Idea For each input ele