MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Lecture 10 Sorting III Linear Bounds Linear Time Sorting 6 006 Spring 2008 Lecture 10 Sorting III Linear Bounds Linear Time Sorting Lecture Overview Sorting lower bounds Decision Trees Linear Time Sorting Counting Sort Readings CLRS 8 1 8 4 Comparison Sorting Insertion sort merge sort and heap sort are all comparison sorts The best worst case running time we know is O n lg n Can we do better Decision Tree Example Sort a1 a2 an 1 2 1 3 2 3 2 3 213 1 3 123 231 132 321 312 Figure 1 Decision Tree Each internal node labeled i j compare ai and aj go left if ai aj go right otherwise 1 Lecture 10 Sorting III Linear Bounds Linear Time Sorting 6 006 Spring 2008 Example Sort a1 a2 a3 9 4 6 Each leaf contains a permutation i e a total ordering 1 2 9 4 a1 a2 1 3 2 3 9 6 a1 a3 2 3 a2 a3 4 6 231 4 6 9 Figure 2 Decision Tree Execution Decision Tree Model Can model execution of any comparison sort In order to sort we need to generate a total ordering of elements One tree size for each input size n Running time of algo length of path taken Worst case running time height of the tree Theorem Any decision tree that can sort n elements must have height n lg n Proof Tree must contain n leaves since there are n possible permutations A height h binary tree has 2h leaves Thus n 2h n lg n Stirling e n lg n n lg e h lg n n lg n 2 Lecture 10 Sorting III Linear Bounds Linear Time Sorting 6 006 Spring 2008 Sorting in Linear Time Counting Sort no comparisons between elements Input A 1 n where A j 1 2 k Output B 1 n sorted Auxiliary Storage C 1 k Intuition Since elements are in the range 1 2 k imagine collecting all the j s such that A j 1 then the j s such that A j 2 etc Don t compare elements so it is not a comparison sort A j s index into appropriate positions Pseudo Code and Analysis k n k n 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 n k Figure 3 Counting Sort 3 Lecture 10 Sorting III Linear Bounds Linear Time Sorting Example Note Records may be associated with the A i s 1 A 4 1 1 B 2 2 3 4 5 3 4 3 3 1 3 4 5 3 4 4 1 2 3 4 C 0 0 0 0 C 1 0 2 2 1 3 C 2 1 1 4 3 5 2 Figure 4 Counting Sort Execution A n A 5 3 C 3 3 B 3 A 5 3 C 3 decr A 4 4 C 4 5 B 5 A 4 4 C 4 decr 4 and so on 4 6 006 Spring 2008
View Full Document
Unlocking...