c Balaji Raghavachari 54 Algorithm Design and Analysis c Balaji Raghavachari 55 Algorithm Design and Analysis Classification of Sorting based on location of data External sorting data is stored in disk Comparison based sorting algorithms Data size is too large for computer s memory Operations used for sorting comparison swap Time is dominated by disk access Most general paradigm applies to all sorting problems Merge sort is the best choice O n log n algorithms Merge Sort Heap sort Internal sorting data is stored within memory O n log n expected time Quick sort Many algorithms are available Merge sort Quick sort Heap sort Insertion sort Counting sort Bucket sort Radix sort Algorithm that runs in O n2 time that should be used only when the data size is small or if the data is almost sorted Insertion sort Choice of algorithm depends on application Make use of knowledge of distribution of data c Balaji Raghavachari 56 Algorithm Design and Analysis Lower bound for comparison based sorting Consider a comparison based sorting algorithm X on n elements Behavior of X on all inputs of size n can be captured by a decision tree c Balaji Raghavachari 57 Algorithm Design and Analysis Summary Comparison based sorting Any algorithm that is comparison based compare and swap requires n log n in the worst case to sort an array of n elements A binary tree in which each internal node represents a comparison of two elements some ai and aj Hence Mergesort and Heapsort are optimal algorithms Edges to children are marked and depending on the result of the comparison Decision tree argument can be extended to prove that comparison based sorting algorithms require at least n log n time to sort half of n permutations of 1 n i e most inputs require n log n time Leaves are represented by permutation of input sequence that corresponds to the sorted order Worst case R T of X height of its decision tree Every permutation of the input has to be represented by a leaf Therefore number of leaves n Pn Height of tree log n k 1 log k n log n Lower bound theorem can be extended to show that the expected R T of randomized algorithms is n log n c Balaji Raghavachari 58 Algorithm Design and Analysis Counting sort Used when elements are in the range 1 k for a small integer k Count how many 1 s how many 2 s etc there are in the given array c Balaji Raghavachari Initialize an array L of k linked lists to be empty For i 1 to n insert A i into L q where q A i key For j 1 to k output elements of L j Running time is O n k which is O n if k O n Algorithm is stable if the order of equal elements is the same as in the input array easily achieved by inserting at the end of the lists Algorithm Design and Analysis c Balaji Raghavachari 61 Algorithm Design and Analysis Bucket sort Algorithm used for sorting statistical samples Radix sort Divide range B0 Bn into n buckets B0 B1 B1 B2 Bn 1 Bn Given an array of n d digit numbers where each digit takes k possible values sort them for i 1 to d do least significant digit to the most Use counting sort on the numbers by looking at only digit i stable sorting is important Loop invariant to show correctness of Radix sort After i passes the array is sorted if we consider only the first i digits For i 1 to n insert A i into bucket k if Bk 1 A i key Bk Sort the elements within each bucket For k 1 to n output the elements in bucket k Algorithm s success depends on two aspects 1 Finding k for a given A i quickly Running time is O d n k If d O 1 and k O n then the running time of Radix sort is O n Counting sort algorithm C j elements of A 1 n less than or equal to j j should occupy B C j 1 1 C j in sorted output for i n downto 1 do reverse order for stable sorting j A i key B C j A i C j Output B For another version of Counting sort see next slide 60 Algorithm Design and Analysis Counting Sort A n Running time is O n k Sort A 1 n with field key integer in 1 k Count how many of each 1 k appear in A for j 1 to k do C j 0 for i 1 to n do C A i key for j 2 to k do C j C j C j 1 Example array A 1 n are records that need to be sorted by field named key whose range is 1 k c Balaji Raghavachari 59 2 Selecting the ranges such that the expected number of elements in each bucket is O 1 Expected R T is O n if both conditions are satisfied
View Full Document
Unlocking...