Time complexity of Sorting Several sorting algorithms have been discussed and the best ones so far Heap sort and Merge sort O n log n Quick sort best one in practice O n log n on average O n2 worst case 1 Time complexity of Sorting Can we do better than O n log n No It can be proven that any comparison based sorting algorithm will need to carry out at least O n log n operations 2 Can we do better Linear sorting algorithms Bucket sort Radix Sort Counting Sort Make certain assumptions about the data Linear sorts are NOT comparison sorts 3 BinSort not binary a k a BucketSort If all keys are 1 K Have array of size K Put keys into correct bin cell of array 4 BinSort example K 5 list 5 1 3 4 3 2 1 1 5 4 5 Bins in array key 1 1 1 1 key 2 2 key 3 3 3 key 4 4 4 key 5 5 5 5 Sorted list 1 1 1 2 3 3 4 4 5 5 5 5 BinSort Pseudocode procedure BinSort List L K LinkedList bins 1 K Each element of array bins is linked list Could also do a BinSort with array of arrays For Each number x in L bins x Append x End For For i 1 K For Each number x in bins i Print x End For End For 6 BinSort Conclusion K is a constant BinSort is linear time K is large e g 232 Impractical 7 BinSort is stable Stable Sorting algorithm Items in input with the same key end up in the same order as when they began Important if keys have associated values Critical for RadixSort 8 Time complexity Bucket initialization O m From array to buckets O n From buckets to array O n Even though this stage is a nested loop notice that all we do is dequeue from each bucket until they are all empty n dequeue operations in all 9 Time complexity Since m will likely be small compared to n Bucket sort is O n Strictly speaking time complexity is O n m 10 Sorting integers Can we perform bucket sort on any array of nonnegative integers Yes but note that the number of buckets will depend on the maximum integer value If you are sorting 1000 integers and the maximum value is 999999 you will need 1 million buckets Time complexity is not really O n because m is much than n Actual time complexity is O m Can we do better 11 Radixes The word radix is used as a synonym for base A radix R representation is the same as a base R representation For example What is a radix 2 representation What is a radix 10 representation What is a radix 16 representation 12 Radixes The word radix is used as a synonym for base A radix R representation is the same as a base R representation For example What is a radix 2 representation Binary What is a radix 10 representation Decimal What is a radix 16 representation Hexadecimal We often use radixes that are powers of 2 but not always 13 Radix sort Two versions MSD Radix sort Most Significant Digit LSD Radix sort Least Siginificant Digit 14 MSD Radix Sort If the radix is R the first pass of radix sort works as follows Create R buckets In bucket M store all items whose most significant digit in R based representation is M Reorder the array by concatenating the contents of all buckets In the second pass we sort each of the buckets separately All items in the same bucket have the same most significant digit Thus we sort each bucket by creating sub buckets of the bucket based on the second most significant digit We keep doing passes until we have used all digits 15 Example Example suppose our items are 3 letter words cat dog cab ate cow dip ago cot act din any Let R 26 This means that we will be creating 26 buckets at each pass What would be the digits of the items that we use to assign them to buckets 16 Example Example suppose our items are 3 letter words cat dog cab ate cow dip ago cot act din any Let R 26 This means that we will be creating 26 buckets at each pass What would be the digits of the items that we use to assign them to buckets What will the buckets look like after the first pass 17 Example Example suppose our items are 3 letter words cat dog cab ate cow dip ago cot act din any What will the buckets look like after the first pass Bucket a ate ago act any Bucket c cat cab cow cot Bucket d dog dip din All other buckets are empty What happens at the second pass 18 Example What happens at the second pass Recursively do MSD Radix on each non empty bucket Bucket a ate ago act any subbucket c act subbucket g ago subbucket n any subbucket t ate Bucket a is rearranged as act ago any ate Repeat same for bucket c and bucket d 19 Programming MSD Radix Sort Sort numbers on most significant digit MSD Initialise R bucket For eaach MSD put the number In bucket sort each of the resulting bins recursively then combine the bins in order 20 Radix sort LSD Idea repeatedly sort by digit perform multiple bucket sorts on S starting with the rightmost digit If maximum value is 999999 only ten buckets not 1 million will be necessary Use this strategy when the keys are integers and there is a reasonable limit on their values Number of passes bucket sort stages will depend on the number of digits in the maximum value 21 Example 1st pass 12 58 37 64 52 36 99 63 18 9 20 12 52 63 64 20 88 47 58 37 18 99 36 47 88 9 20 12 52 63 64 36 37 47 58 18 88 99 9 22 Example 2nd pass 20 12 52 63 64 36 37 47 58 18 88 99 9 9 9 12 36 52 63 18 20 37 47 58 64 88 99 12 18 20 36 37 47 52 58 63 64 88 99 23 Example 1st and 2nd passes 12 58 37 64 52 36 99 63 18 9 20 88 47 sort by rightmost digit 20 12 52 63 64 36 37 47 58 18 88 9 99 sort by leftmost digit 9 12 18 20 36 37 47 52 58 63 64 88 99 24 Radix sort and stability Radix sort works as long as the bucket sort stages are stable sorts 25 Radix sort and stability Stable sort in case of ties relative order of elements are preserved in the resulting array Suppose there are two elements whose first digit is the same for example 52 58 If 52 occurs before 58 in the array prior to the sorting stage 52 should occur before 58 in the resulting array This …
View Full Document
Unlocking...