Lower Lower Bounds Bounds Sorting Sorting in in Linear Linear Time Time Comp 122 Spring 2004 Comparison based Sorting Comparison sort Only comparison of pairs of elements may be used to gain order information about a sequence Hence a lower bound on the number of comparisons will be a lower bound on the complexity of any comparison based sorting algorithm All our sorts have been comparison sorts The best worst case complexity so far is n lg n merge sort and heapsort We prove a lower bound of n lg n or n lg n for any comparison sort implying that merge sort and heapsort are optimal nsort 2 Comp 122 Lin Devi Decision Tree Binary tree abstraction for any comparison sort Represents comparisons made by a specific sorting algorithm on inputs of a given size Abstracts away everything else control and data movement counting only comparisons Each internal node is annotated by i j which are indices of array elements from their original positions Each leaf is annotated by a permutation 1 2 n of orders that the algorithm determines nsort 3 Comp 122 Lin Devi Decision Tree Example For insertion sort operating on three elements nsort 4 1 2 2 3 1 3 1 2 3 1 3 1 3 2 2 1 3 3 1 2 2 3 2 3 1 3 2 1 Contains 3 6 leaves Comp 122 Lin Devi Decision Tree Contd Execution of sorting algorithm corresponds to tracing a path from root to leaf The tree models all possible execution traces At each internal node a comparison ai aj is made If ai aj follow left subtree else follow right subtree View the tree as if the algorithm splits in two at each node based on information it has determined up to that point When we come to a leaf ordering a 1 a 2 a n is established A correct sorting algorithm must be able to produce any permutation of its input nsort 5 Hence each of the n permutations must appear at one or more of the leaves of the decision tree Comp 122 Lin Devi A Lower Bound for Worst Case Worst case no of comparisons for a sorting algorithm is Length of the longest path from root to any of the leaves in the decision tree for the algorithm Which is the height of its decision tree A lower bound on the running time of any comparison sort is given by nsort 6 A lower bound on the heights of all decision trees in which each permutation appears as a reachable leaf Comp 122 Lin Devi Optimal sorting for three elements Any sort of six elements has 5 internal nodes nsort 7 1 2 2 3 1 3 1 2 3 1 3 1 3 2 2 1 3 3 1 2 2 3 2 3 1 3 2 1 There must be a wost case path of length 3 Comp 122 Lin Devi A Lower Bound for Worst Case Theorem Theorem8 1 8 1 Any Anycomparison comparisonsort sortalgorithm algorithmrequires requires n nlg lgn n comparisons comparisonsin inthe the worst worstcase case Proof From previous discussion suffices to determine the height of a decision tree h height l no of reachable leaves in a decision tree In a decision tree for n elements l n Why In a binary tree of height h no of leaves l 2h Prove it Hence n l 2h nsort 8 Comp 122 Lin Devi Proof Contd nsort 9 n l 2h or 2h n Taking logarithms h lg n n n e n Stirling s approximation Eq 3 19 Hence h lg n lg n e n n lg n n lg e n lg n Comp 122 Lin Devi Non comparison Sorts Counting Sort Depends on a key assumption numbers to be sorted are integers in 0 1 2 k Input A 1 n where A j 0 1 2 k for j 1 2 n Array A and values n and k are given as parameters Output B 1 n sorted B is assumed to be already allocated and is given as a parameter Auxiliary Storage C 0 k Runs in linear time if k O n Example On board nsort 10 Comp 122 Lin Devi Counting Sort A B k CountingSort A CountingSort A B B k k 1 1 for forii 00to tokk 2 2 do doC i C i 00 3 3 for forjj 11to tolength A length A 4 4 do doC A j C A j C A j C A j 11 5 5 for forii 11to tokk 6 6 do doC i C i C i C i C i C i 1 1 7 7 for forjj length A length A downto downto11 8 8 do doB C A B C A jj A j A j 9 9 C A j C A j C A j 1 C A j 1 nsort 11 Comp 122 O k O n O k O n Lin Devi Algorithm Analysis The overall time is O n k When we have k O n the worst case is O n for loop of lines 1 2 takes time O k for loop of lines 3 4 takes time O n for loop of lines 5 6 takes time O k for loop of lines 7 9 takes time O n Stable but not in place No comparisons made it uses actual values of the elements to index into an array nsort 12 Comp 122 Lin Devi What values of k are practical Good for sorting 32 bit values No Why 16 bit Probably not 8 bit Maybe depending on n 4 bit Probably unless n is really small Counting sort will be used in radix sort nsort 13 Comp 122 Lin Devi Radix Sort It was used by the card sorting machines Card sorters worked on one column at a time It is the algorithm for using the machine that extends the technique to multi column sorting The human operator was part of the algorithm Key idea sort on the least significant digit first and on the remaining digits in sequential order The sorting method used to sort each digit must be stable If we start with the most significant digit we ll need extra storage nsort 14 Comp 122 Lin Devi nsort 15 An Example Input 392 356 446 928 631 532 495 After sorting on LSD 631 392 532 495 356 446 928 After sorting on middle digit After sorting on MSD 928 631 532 446 356 392 495 356 392 446 495 532 631 928 Comp 122 Lin Devi Radix Sort A d RadixSort A RadixSort A d d 1 1 for forii 11to todd 2 2 do douse useaastable stablesort sortto tosort sortarray arrayAAon ondigit digitii Correctness of Radix Sort By induction on the number of digits sorted Assume that radix sort works for d 1 digits Show that it works for d digits Radix sort of d digits radix sort of the low order d 1 digits followed by a sort on digit d nsort 16 Comp 122 Lin Devi …