Programming is an extremely wide world. As software developers we just have time to know a minuscule portion of the whole. This constraint prevents us from discovering interesting, but less popular areas.
Sorting algorithms are not an exception, we have all heard about QuickSort, MergeSort or BubbleSort, anyhow, there are many alternative options.
Radix Sort Algorithm is one of those alternatives.
Here’s what you need to know about the Radix Sort Algorithm, from strategy and step by step resolution flow, to code implementation in Java.
The idea of Radix Sort is to do digit by digit sort. Starting from least significant digit to most significant digit. It is a simple concept to understand, but I personally think it gets easier with an example. Let’s say we want to sort the following arra,
Since the element with the maximum value has three digits, the array will be sorted after three stages, one for each digit.
First Stage, Units.
During the first iteration, numbers are sorted based on their least significant digit. The first set of numbers is always the same as the previous stage, but with the digit which is going to be compared underlined, if there is no number above the underscore, zero will do the comparison.
Eleven goes before nine hundred and twenty-one because it is on its left. The sort is done from left to right, from lowest to highest on underlined digits.
Second Stage, Dozens.
Second iterations sorts numbers based on their next more significant digit,
At this moment, only three digits numbers are not sorted yet. Because two stages have been completed, every number composed of two or less digits is sorted.
Third Stage, Hundreds.
Lastly, numbers are sorted based on their most significant digit. During this third stage, the majority of numbers compare to each other with zero as their hundred digits.
Finally, the array is completely sorted.
The code is divided into three images, explained individually.
Firstly, there is the main method which calls the algorithm with the array to be sorted, the same as the previous example, and it’s length.
Function radixSort receives the array we want to sort, and it’s length. This function’s purpose is to call the algorithm itself as many times as digits the maximum value has (MVD).
Maximum value is obtained using java.util.Arrays library, but it could be done by implementing a simple function which returns the maximum value of an array. Personally, I prefer this one-line solution.
To iterate as many times as MVD, a for loop is controlled by exponent integer, which gets multiplied by ten after each loop iteration. The for loop stops when the exponent is not lower than ten to the MVD power. Function countSort is called on every iteration.
Function countSort receives three parameters, the array, it’s length, and the current exponent. Two integer arrays are declared, output stores sorting changes made to array, and count is used to save repetitions per exponent. This process takes place during the first loop, it calculates how many numbers have the units digit equal to zero, and saves it in count, same with one, and so on. For example, previous array Units Stage would set these values in count array after first loop,
Second loop changes count array values too, each position is set with the accumulated value. The goal is to store in count[x], how many numbers have an exponent exp digit equal or lower than x. This is how count array after second loop would look like with our example,
The last part of the algorithm relocates each number of the original array, based on how many values are equal or lower than it, this information is consulted in the array count.
In our example, nine hundred and twenty-one is the first number to be relocated, because the for loop iterates backwards. Nine hundred and twenty-one’s units digit is one, looking at count, we can see that there are three numbers which have units digit equal or lower to one, the algorithm subtract one to skip the number itself, and relocate nine hundred and ninety-one at output. Finally, the output array is copied to the array, and radixSort’s loop continues.
Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for the decimal system, b is ten. The value of d depends on k. If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b) * logb(k)), which approximates to O(nlogn).
Now you know a new different path to accomplish your sorting tasks, If you want different results you have to try different approaches. In case you have any doubts or you want to give me some feedback, which I would appreciate, contact me by my LinkedIn