Radix Sort is possibly the chillest person you will ever meet.
The third child of the family patriarchs Selection and Merge Sorts, he greets every problem, every family squabble, every thing that ever happens to him with "Cool, man". He once witnessed a car crash and later described the event as "two cars having a meeting of the minds" (the family hasn't let him live this down). A peculiar scent seems to pervade areas he inhabits. He's the most easy-going person at the reunion.
At least, that's what he wants you to think.
In reality, at this moment, he's terrified. Terrified that someone will find out that he's a fraud. That job as an auto mechanic the family still thinks he has? He was fired last week over something stupid. Only his beloved wife Bead Sort knows, and he is petrified that someone else will discover his secret. With no way to provide for his family, he feels like a failure. Beady tried to help, tried to make him feel like he contributes, but he seems to only shrink further away from her.
He's holding his breath, praying no one finds out, barely clinging to his friendly, chill facade.
The Rundown
- Created By: Unknown, possibly Herman Hollerith (1887)
- Type: Distribution
- Stable? Depends on implementation
- Worst-Case: O(w * n)
- Space Complexity: O(w + n)
- Sample Project: Over on GitHub
exceptionnotfound
Algorithm
- SORT the numbers into buckets based on the value of the least-significant digit.
- SORT the numbers in each bucket again, based on the value of the next-least-significant digit.
- CONTINUE UNTIL there are no significant digits left.
Visualization
Suppose we have the following array:
{ 5419, 13, 384, 201, 7, 2232, 3, 81, 19, 4029 }
Radix Sort's algorithm tells us we need to sort on the least-signification digit. We should therefore sort based on these values:
{9, 3, 4, 1, 7, 2, 3, 1, 9, 9}
Doing that sort results in this intermediate array:
{ 201, 81, 2232, 13, 3, 384, 7, 5419, 19, 4029 }
We now need to sort on the second-least-significant digit. Problem is, some of these numbers (e.g. 3 and 7) don't have such a digit. We therefore need to impose a digit at that position of 0.
{ 201, 81, 2232, 13, 03, 384, 07, 5419, 19, 4029 }
We can now sort based on the second-least-significant digit, resulting in:
{ 201, 03, 07, 13, 19, 5419, 4029, 2232, 81, 384 }
We need to do this twice more; once for the third-least-significant digit:
{ 3, 7, 13, 19, 4029, 81, 201, 2232, 384, 5419 }
And, finally, we sort based on the most-significant digit, resulting in the final sorted array:
{ 3, 7, 13, 19, 81, 201, 384, 2232, 4029, 5419 }
What we have just done is technically called a least-significant digit radix sort.
The audibilization of this sort is pretty neat, check it out:
C# Implementation
class RadixSort
{
public static void Main()
{
int[] array = { 330, 8, 27, 4419, 55, 816, 419, 77, 622, 1234, 6, 9, 241, 1, 35, 7733, 4, 69 };
int length = array.Length;
Console.WriteLine("Radix Sort");
CommonFunctions.PrintInitial(array);
int max = array.Max();
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, length, exp);
}
CommonFunctions.PrintFinal(array);
Console.ReadLine();
}
//This is a modified version of Counting Sort from an earlier post
//We need to do Counting Sort against each group of integers,
//where the groups are made based on the position of significant digits.
//So, we use Counting Sort on the least-significant digit, then the next-least, etc.
//After that, we concatenate the groups together to form the final array.
public static void CountingSort(int[] array, int length, int exponent)
{
//Create a new "output" array
int[] output = new int[length]; // output array
int i;
//Create a new "counting" array which stores the count of each unique number
int[] count = new int[10];
for (i = 0; i < 10; i++)
{
count[i] = 0;
}
for (i = 0; i < length; i++)
{
count[(array[i] / exponent) % 10]++;
}
//Change count[i] so that count[i] now contains actual position of
//this character in the output array.
for (i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
//Build the output array.
//This is the tricky part.
for (i = length - 1; i >= 0; i--)
{
output[count[(array[i] / exponent) % 10] - 1] = array[i];
count[(array[i] / exponent) % 10]--;
}
//Copy the output array to the final array.
for (i = 0; i < length; i++)
{
array[i] = output[i];
}
}
}Time and Space Complexity
This algorithm has a unique worst-case time complexity: O(w * n), where w is the number of bits required to store each value. This makes intuitive sense; it means that as the number of significant digits grows, the time needed for the algorithm to complete also grows.
The space complexity for this algorithm is even more obvious: O(w + n), which means that the space required is a direct function of the number of digits needing to be sorted.
Both of these values are relatively low compared to other sorting algorithms. Because of this, Radix Sort is a pretty useful real-world algorithm. In fact, because Radix Sort doesn't actually need the values being sorted to be integers, we can use this algorithm to sort various things, including letters and words.
Summary
Radix Sort is one of the more useful real-world sorts; because it operates on least-significant digit, it can be used to sort quite a lot more than just numbers. But be aware; beneath the chill, "whatever, man" surface, he's quietly petrified that someone he cares about is going to discover his secret.
The final member of the family, Bucket Sort, is our last entry in this series, and he really wishes he could own a boat. There's just one problem with that.
Matthew Jones
Don't forget to check out the sample project over on GitHub!
Happy Coding!
