Radix Sort - A Non-Comparison Based Sorting Algorithm
Explore the fascinating concept of Radix Sort, a non-comparison based sorting algorithm that relies on sorting by individual digits. Follow the step-by-step process of bucketing numbers without the need for direct comparisons, leading to a sorted list without traditional sorting methods. Witness the magic of Radix Sort through detailed examples and illustrations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
RadixSort My favorite sorting algorithm
Noncomparison Based Sorting Most sorting algorithms assume that you have to compare data to sort. E.g., Is x before y? (x < y) Can we sort without having to compare numbers? YES! Woah! 2
You have a set of numbers to sort Step 1: Make 10 buckets : Indices 0 through 9 (an array of size 10, with each index able to hold multiple values (maybe linked list, 2-d array?) Step 2: Go through the numbers. Using their LEAST SIGNIFICANT DIGIT place each number in the bucket associated with its least significant digit don t sort when placing in buckets. Just shove each number at the end of its bucket list (bucket list haha) In other words, the LSD becomes the index into the bucket array But if two or more numbers end up in the same bucket, just plop the next number with the same LSD at the end of that bucket s list (don t sort at all when placing in buckets!) Step 3: Re-merge the list, and repeat step 2 for the 2nd least significant digit. Step 4: Keep repeating until we hit the largest number s most significant digit Voila! Sorted list! 3 (This is easier to see than explain )
Sorting: 344, 328, 402, 624, 188, 614, 202, 16, 12, 8 Bucket array (pass 1): assigning to buckets based on least significant digit! 0 1 2 3 index 402 4 5 6 7 8 9 344 624 16 328 188 202 8 12 614 Reassembled Array: 402,202,12,344,624,614,16,328,188,8 Bucket array (pass 2): assigning to buckets based on second least significant digit 0 1 2 3 4 index 5 6 7 8 9 188 344 12 402 202 624 614 16 328 8 Reassembled Array: 402,202,8,12,614,16,624,328,344,188 Bucket array (pass 3): assigning to buckets based on third least significant digit index 202 8 328 344 0 1 2 3 4 5 6 7 8 9 188 402 614 624 12 16 Reassembled Array: 8,12,16,188,202,328,344,402,614,624 !!! 3 passes!!!!! No comparisons!!! A MIRACLE HAPPENED!!!
Radix Sort (another example!) Let s try it: 427, 496, 834, 222, 333, 444, 595, 582, 767, 294 First pass: 0 1 2 222->582 333 3 4 834->444->294 5 595 6 496 7 427->767 8 9 Second Pass: 0 1 2 222,427 333,834 3 4 444 5 6 767 7 8 582 9 294,594,496 Third Pass: 0 1 2 222,294 333, 3 4 427,444,496 5 582594 6 7 767 8 834 9 5
Try: (Remember, pad on the left with 0s) 647, 315, 16, 14,359, 453,203,235 First Pass: 453,203 14 315,235 16 647 359 Second Pass: 203 14,315,16 235 647 453,359 Third Pass: 14,16 203,235 315,359, 453 647 6
Radix Sort Analysis Coolest algorithm ever!!! The algorithm is non-comparison based Time Analysis: Each pass must go through all n numbers to put each number in the correct bucket The number of passes depends on the biggest number We must make a pass for each digit in the largest number So the total time is O(n*k) If there are k digits in the largest number Drawbacks: Either: implementing an array of linked lists isn t straightforward or Space a n x n matrix so we know all the values will fit in each bucket Also: Not great for the following sequence of numbers: 7 324,766,21,813,962,12,131,32,540,678,323928343982634287632843298428374, 422, 8 (why?)
RadixSort: Take-Aways Coolest algorithm ever!!! non-comparison based Place values in buckets based on the value s digits Running time: O(n*k) Where k is the number of digits in the largest number Good for sorting large numbers Not great for sorting numbers where one number is significantly greater than all the other numbers
