# Data Structures & Algorithms Radix Sort Key Comparison Data Structures & Algorithms Radix Sort Key Comparison Often the key has structure Often only part of the key is needed to decide the order Processing one piece of the key at a time is radix sort Bytes of binary numbers Characters in strings Digits in decimal numbers Advantage from limited range of each piece! Radix Sorting Treat keys as numbers represented in a base-R system for various values of R (the radix) Partially sort based on each piece Decimal numbers R =10 Binary numbers R = 2k Character strings R = 256 or 128 Pretty much anything: bits Fortunately, C and C++ allow easy access to bits of representations.... Radix Sort Approaches MSD Most Significant Digit

a.k.a. BucketSort or BinSort Examine keys in left-to-right order Work with most significant digits first Partially sort (a la QuickSort) Examine the minimum amount of information to get the sort done LSD Least Significant Digit Traditional RadixSort Examine keys in right-to-left order Work with least significant digits first Getting at the Digits If string or array, just use array index bth part is just a[b], or a[N-b] If binary integer, bth digit of number a is [a/Rb] % R If real between 0 and 1 bth digit of number a is [aRb] % R BucketSort Example 1A 09

03 25 3C 17 13 39 24 18 100000 1A 09 03 18 13 17 3C

39 24 25 010000 03 09 1A 18 13 17 25 24 39 3C 001000

03 09 17 13 18 1A 25 24 000100 03 09 13 17 18 1A 24

000010 03 09 13 17 18 1A 24 000001 03 09 13 17 18 1A 24 25 25

25 39 3C 39 3C 39 39 3C 3C MSD Radix Sort Tree ALL >1F <20 >0F <10 <8 03 >7 09

>17 <18 <14 13 >13 17 >2F <30 <1C <28 >1B <24 <14 >13 18 1A >27 >37

<38 <3A >3B 39 3C >23 <25 >24 24 25 LSD Radix Sort Work from right to left, starting with least significant digit Not intuitively obvious it works... Requires a stable sort to work Correctness: After items in order on i LSBs (in stable manner): two keys are in order based on key digits examined so far First digit is different put into order this

pass First digit same stability LSD Radix Sort Work from right to left, starting with least significant digit Not intuitively obvious it works... Requires a stable sort to work Correctness: After items in order on i LSDs w-i MSDs same => stability keeps order w-i MSDs differ => later pass will sort Radix Sort Performance Takes time proportional to # passes Takes time proportional to # elements Total time = O(Nw) where w is the number of digits (key pieces) Binary QuickSort examines about N lg N bits, on average, when sorting keys of random bits