Searching and Sorting Algorithms in Javascript — Part 7 (Radix Sort).
If you’ve been been following this series from part one, you must have realized that, in the end, we’re just looking for better ways to do the same thing. The method you choose to apply basically depends on the problem at hand.
Of the several ways there is to arrange (or sort) the items of a list (or an array), Radix Sort is one of the very unique ones. It takes a very different approach when performing this task of arranging items.
INTRODUCTION TO RADIX SORT
What is Radix sort exactly and how is it different from all the other algorithms we’ve mentioned so far?
If you carefully look at all the other algorithms we’ve discussed so far (from bubble sort to quick sort), you’ll quickly realize that at some point, we’re comparing 2 numbers and deciding which one is greater or smaller. These algorithms are all grouped under something called “the Comparison sorting algorithms”.
When dealing with Radix Sort Algorithm, we’re not actually comparing 2 numbers at any point in time to decide which is greater or lesser. It takes a very different approach, it uses the fact that the information about a given number is engraved in the number of digits the number has. Take a number for instance (say 1022). 1022 is a 4 digit number and we can be very sure that 1022 (a 4 digit number) is always greater than any 3 digit number.
This basic information about the number of digits a particular number has can be very powerful (you’ll see when we start implementing the algorithm) and it forms the basis of the building blocks of the Radix Sort Algorithm. This might be a long read so, stick with me to the end and you’ll see the light at the end of the tunnel!
A Microscopic View Into Radix Sort Algorithm
Now, we’re getting into the technicalities of how Radix sort algorithm works.
The way Radix sort perform its job is to group its members. Like I said earlier, it doesn’t compare numbers, so, you might be wondering: “How exactly does it group these numbers?”. Let me walk you through with an illustration.
Say we want to sort an array of numbers: [4, 9, 28, 68, 86, 8156, 4132,408, 1556,3556,593].
First we create a list of buckets with a pointer to each bucket (from 0–9) like the diagram below:
Next, we loop through our list of numbers and arrange them in the buckets using the following rules.
- Starting from the right, we take the first digit of the current number in the loop and we then push that number to the corresponding bucket. Say our current number is 4132, the first digit (starting from the right) is 2 so, we push 4132 to the bucket with the pointer number 2.
On first pass, we have the following result.
2. After arranging them, we then build a new array from the bucket. We’ll push elements into this new array following the order of our bucket.
Now, we have a new array that looks like this:
3. We’ll group the numbers into the buckets again only that, this time around, we’ll be using the second digit (starting from the right). You might notice that some numbers are only one digit numbers, just add zeroes to make up for that so in this case, 9 and 4 will be 09 and 04 respectively which makes their second digit 0 (if you’re starting your count from the right). Always have in mind that we’re always counting from the right.
After the second pass, we then have the following group of numbers:
4. We then rebuild another list from our new bucket of items. Now, we have a new array (or list) like so:
(You can see that our list is already getting sorted some how).
5. You’ll then repeat this process using the third digit of each number until you’ve exhausted all the possible digits in each number. The loop has a determinable number of times it should run. So, in your list of items, if the largest number has 7 digits, then you’ll run the loop 7 times. In simple terms, the loop runs as many times as the amount of digits in the largest number.
Does that make any sense? If it doesn’t, I assure you it’ll make more sense when you check the code implementation.
NOW WHAT?
Well, we’ve seen how the algorithm works so, let’s implement this in code.
The code might look a bit intimidating at first but, If you understand the process initially explained, you shouldn’t really have much problem understanding how the code works.
Theoretically, Radix sort tend to be faster than the other sorts that uses comparison technique to sort their elements but, there are few arguments around that. Personally, I like radix sort as it takes a more intuitive approach to solving this problem. And it’s a fun one as well.
Radix Sort’s time complexity of O(nd), where n is the size of the array and d is the number of digits in the largest number.
Well, that’s all I have to say about sorting algorithms. Now, we move to searching algorithms (starting with linear search).
See you on the next one!
