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

Recently Viewed Presentations

• Section 2 Basic fMRI Physics Other Resources Recipe for MRI History of NMR History of fMRI Necessary Equipment The Big Magnet Magnet Safety Subject Safety Protons Protons align with field Radio Frequency Larmor Frequency RF Excitation Cox's Swing Analogy Relaxation...
• Pilgrims believed they were elected by God for salvation and they wanted to worship only with other "saints" who had also been saved by God. Puritans were followers of the teachings of Calvin and believed, like the Separatists, that man...
• 中国支线航空调查报告 Survey Report on China's Regional Aviation 为什么要进行中国支线航空调查？ Purposes of China's Regional Aviation Survey 帮助各位挖掘中国航空市场的潜力，了解中国旅客对支线航空的需求，寻找合适的合作伙伴。
• TO LAND - e.g. walking over someone's land without their consent - damage to land irrelevant, not a required element. TO CHATTELS - e.g. using or interfering with the property of another without their consent - damage to property must...
• Mendel and his peas: experiment. Terminology of chromosomes and genes, non-existence for Mendel. Mendel described the basic patterns of inheritance before the mechanism for inheritance was even discovered.. Controlled reproduction of plants and studied traits expressed in offspring.
• High Protein Diet. Design: 307 obese adults were randomized to LCHP or low fat diet for 24 months. LCHP diet from . Dr. Atkins New Diet Revolution (2002). Low fat diet was 1200-1800 cal/day 55% CHO, 30% fat, 15% protein....
• A piece of Valencia
• A body of mass (m) subject to a force (F) ... Biology is the scientific study of all forms of life, or all types of organisms. An organism is any individual living thing. Which of these is a living thing?...