6 006 Introduction to Algorithms Lecture 10 Prof Constantinos Daskalakis CLRS 8 1 8 4 Menu Show that n lg n is the best possible running time for a sorting algorithm Design an algorithm that sorts in n time Hint maybe the models are different Comparison 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 merge sort heapsort The best running time that we ve 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 A recipe for sorting n numbers a1 a2 an Nodes are suggested 2 3 comparisons i j means 123 1 3 compare ai to aj for i j 1 2 n 132 1 2 312 213 1 3 2 3 231 Branching direction depends on outcome of comparisons Leaves are labeled with permutations corresponding to the outcome of the sorting 321 Decision tree example Sort a1 a2 a3 9 4 6 1 2 9 4 2 3 123 1 3 213 1 3 132 312 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 9 6 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 4 6 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 2 3 231 321 4 6 9 Each leaf contains a permutation 1 2 n to indicate that the ordering a 1 a 2 a n has been established Decision tree model A decision tree can model the execution of any comparison sort One tree for each input size n A path from the root to the leaves of the tree represents a trace of comparisons that the algorithm may perform The running time of the algorithm the length of the path taken Worst case running time height of tree Lower bound for decisiontree sorting Theorem Any decision tree that can sort n elements must have height n lg n Proof Hint how many leaves are there The tree must contain n leaves since there are n possible permutations A height h binary tree has 2h leaves Thus 2h n h lg n lg n e n n lg n n lg e n lg n lg is mono increasing Stirling s formula Sorting in linear time Counting sort No comparisons between elements Input A 1 n where A j 1 2 k Output B 1 n a sorted permutation of A Auxiliary storage C 1 k Counting sort for i 1 to k do C i 0 for j 1 to n do C A j C A j 1 for i 2 to k do C i C i C i 1 for j n downto 1 do B C A j A j C A j C A j 1 store in C the frequencies of the different keys in A i e C i key i now C contains the cumulative frequencies of different keys in A i e C i key i using cumulative frequencies build sorted permutation Counting sort example one index for each possible key stored in A A B 1 2 3 4 5 4 1 3 4 3 1 C 2 3 4 Loop 1 initialization A 1 2 3 4 5 4 1 3 4 3 B for i 1 to k do C i 0 C 1 2 3 4 0 0 0 0 Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 0 0 0 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 0 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 1 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 1 2 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 B for j 1 to n do C A j C A j 1 C i key i A parenthesis a quick finish A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 B Walk through frequency array an place the appropriate number of each key in output array A parenthesis a quick finish 1 2 3 4 5 A 4 1 3 4 3 B 1 C 1 2 3 4 1 0 2 2 A parenthesis a quick finish 1 2 3 4 5 A 4 1 3 4 3 B 1 C 1 2 3 4 1 0 2 2 A parenthesis a quick finish 1 2 3 4 5 A 4 1 3 4 3 B 1 3 3 C 1 2 3 4 1 0 2 2 A parenthesis a quick finish 1 2 3 4 5 A 4 1 3 4 3 B 1 3 3 4 4 C 1 2 3 4 1 0 2 2 B is sorted but it is not stably sorted Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 B for j 1 to n do C A j C A j 1 C i key i Loop 3 cumulative frequencies A 1 2 3 4 5 4 1 3 4 3 B for …
View Full Document
Unlocking...