Lecture 12 Sorting.ppt

Lecture 12: Sorting ab? y n cd? cd? ca? da? cb? db? b?ad?c b?ab?d?c db?ad?c cabcd ab?cd Ask only questions you don’t know answers to. bc? aba?cd ab a?cd c?b bd? a?cd?b a?c?bd 5 compares 4 compares Lecture 12: Sorting A different strategy, insertion sorts, may get lucky. ab? y n bc? cd? abcd 3 compares Lecture 12: Sorting ab? y n bc? cd? abcd But it may be unlucky. ab c?b ac? c?ab bd? d?b c?ab ad? d?a c?ab cd? 6 compares d?c?ab Lecture 12: Sorting Consider all possible sorting trees.How many leaves must a sorting tree have to distinguish allpossible orderings of n items? a[0]a[1] ? Lecture 12: Sorting How many leaves must there for a sorting tree for n items? a[0]a[1] n!, the number of different permutations. Lecture 12: Sorting Theorem: A binary tree with K leaves must have depth at least ?log2 K?. In other words, a BT with k leaves and depth d has d = ?log2 K? or K = 2d Proof: Prove by induction that a tree of depth d can have at most, 2d leaves.Base: for d=0, there is 1 leaf.Suppose true for d, consider tree of depth d+1. x y BIH: x and y have at most 2d leaves so whole tree has at most 2*2d = 2d+1 leaves. Now the shortest trees with K leaves must be “perfect” and their depth will be ?log2 K? Lecture 12: Sorting So a tree with n! leaves has depth at least lg n!. Notice that depth = the maximum number of tests one might have to perform.lg n! = lg n(n-1)(n-2)…1 = lg n + lg n-1 + lg n-2 + … + lg 1 ? lg n + … + lg(n/2) ? (n/2) lg(n/2) ? (n/2) lg n - n/2 = W(n lg n)So any sort algorithm takes W(n lg n) comparisons. Lecture 12: Sorting Is there a way to sort without using binary comparisons? Ternary comparisons, K-way comparisons. The basic W(n log n) result will still be true, because W(log2 x)= W(logk x). Useful speed-up heuristic: use your data as an index of an array. Lecture 12: Sorting Consider sorting tray of letters int counts[26]; int j = 0; for(int i=0; i26; i++) counts[i]=0; for(j=0; jtray.length; j