If you’re a programmer, you’ve probably heard of the radix sort. But what is it, exactly? And how can you use it in your code? In this article, we’ll take a closer look at the radix sort in C#, learn how to implement it, and analyze its time and space complexity.
Let’s dive in.
What is Radix Sort?
Radix sort is an efficient sorting algorithm that sorts numbers by checking their digits one at a time, starting with the least significant digit and moving to the most significant digit.
Besides that, it is a non-comparative sorting algorithm, meaning that it does not compare the values of the numbers being sorted. However, it uses counting sort as its “inner algorithm” to perform the sorting process.
Let’s take a deep dive and learn how radix sort works.
How Does Radix Sort Algorithm Work?
Let’s look at an example of how radix sort works. We will use the following set of numbers:
int[] array = {110, 1, 21, 53, 8, 98, 26, 163, 38, 897};
The algorithm starts sorting the elements by first checking the least significant digit. After sorting the array based on the one’s place digit, the array becomes:
110, 1, 21, 53, 163, 26, 897, 8, 98, 38
Next, we are going to sort the array based on its ten’s place digit, which yields this result:
01, 08, 110, 21, 26, 38, 53, 163, 897, 98
Since 897 is our largest number, the iteration stops after checking the hundred’s place digit:
001, 008, 021, 026, 038, 053, 098, 110, 163, 897
Let’s learn how to implement the radix sort algorithm in C#.
How to Implement Radix Sort in C#?
Since radix sort is not a comparative algorithm, we have to check the number of digits that the largest number in the array has. Therefore, let’s write a GetMaxVal() method that takes an array and its size as inputs and returns the largest integer in that array:
public static int GetMaxVal(int[] array, int size)
{
var maxVal = array[0];
for (int i = 1; i < size; i++)
if (array[i] > maxVal)
maxVal = array[i];
return maxVal;
}
The GetMaxVal() method iterates through the array from the first element to the last one while updating the value of maxVal, which we are going to need as we implement the radix sort algorithm.
Next, we are going to write a method RadixSort() that takes an array and its size as inputs and returns a sorted array:
public int[] RadixSort (int[] array, int size)
{
var maxVal = GetMaxVal(array, size);
for (int exponent = 1; maxVal / exponent > 0; exponent *= 10)
CountingSort(array, size, exponent);
return array;
}
We can see that the process starts by getting the largest integer in the array by invoking GetMaxVal(). Once we get the largest integer in the array, we invoke the counting sort method for every exponent.
exponent is calculated as 10^i where i is the current digit. We iterate through the exponents until we reach the largest exponent, which we determine from maxVal.
Next, we are going to pass array, size and exponent as inputs to CountingSort():
public static void CountingSort(int[] array, int size, int exponent)
{
var outputArr = new int[size];
var occurences = new int[10];
for (int i = 0; i < 10; i++)
occurences[i] = 0;
for (int i = 0; i < size; i++)
occurences[(array[i] / exponent) % 10]++;
for (int i = 1; i < 10; i++)
occurences[i] += occurences[i - 1];
for (int i = size - 1; i >= 0; i--)
{
outputArr[occurences[(array[i] / exponent) % 10] - 1] = array[i];
occurences[(array[i] / exponent) % 10]--;
}
for (int i = 0; i < size; i++)
array[i] = outputArr[i];
}
Let’s understand how the CountingSort() method works:
First, we define and initialize two arrays outputArr and occurrences, which are going to come in handy during the sorting process:
var outputArr = new int[size];
var occurences = new int[10];
for (int i = 0; i < 10; i++)
occurences[i] = 0;
We set all the elements in occurrences to zero as we prepare to update it when we start the sorting process. The next step is to determine the count of the occurrences of each array element, which we calculate using the current exponent:
for (int i = 0; i < size; i++)
occurences[(array[i] / exponent) % 10]++;
Now, we change occurrences[i] in such a manner that occurrences[i] now stores the actual position of the digit in the outputArr:
for (int i = 1; i < 10; i++)
occurences[i] += occurences[i - 1];
Once we have these array positions stored in occurrences, we can now set the elements based on their sorted positions as we add them to outputArr :
for (int i = size - 1; i >= 0; i--)
{
outputArr[occurences[(array[i] / exponent) % 10] - 1] = array[i];
occurences[(array[i] / exponent) % 10]--;
}
We can now copy the elements in outputArr over to array to complete the sorting process:
for (int i = 0; i < size; i++)
array[i] = outputArr[i];
Finally, we can verify that the RadixSort() method sorts a given unsorted array accurately:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new InsertionSortMethods();
var sortedArray = sortFunction.SortArray(array, array.Length);
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);
Space and Time Complexity of Radix Sort Algorithm
From our implementation, we can see that radix sort requires O(n + k) space with n being the number of elements and k being the space used to hold counts, indices, and output arrays. However, since k is constant, the space complexity of the algorithm is O(n).
Best-Case Time Complexity
The best-case time complexity of radix sort occurs when all the elements in the array have the same number of digits.
Therefore, the algorithm has a best-case time complexity of O(d*n), where d is the number of digits in the largest number and n is the number of elements in the array.
Average-Case Time Complexity
The radix sort algorithm encounters the average-case time complexity scenario when the array elements have digits that are distributed uniformly. Assuming we are going to make ‘p’ passes and each digit is going to have up to ‘d’ different values, we can compute the average time complexity of the radix sort algorithm to be T(n) = p(n+d) where n is the number of elements.
Therefore, the radix sort algorithm has an average-case time complexity of O(p(n+d)).
Worst-Case Time Complexity
The radix sort algorithm encounters a worst-case time complexity scenario when all the array elements in the array have the same number of digits except one, which has a large number of digits. This means, assuming the largest element has n number of digits, the algorithm has a runtime of O(n2).
On the other hand, since we also use counting sort in our implementation, its worst-case runtime is O(n+b), which can be summarized as O(n). From our implementation, assuming we call counting sort d times with d = [
O(logb(mx)(n+b)).
Advantages of Radix Sort Algorithm
The radix sort algorithm is fast when the range of the array elements is minimal.
It is ideal for use in suffix-array construction algorithms such as Manber’s algorithm and DC3 algorithm.
It is stable (maintains the original order of elements with equal values) unlike other sorting algorithms such as quicksort.
Disadvantages of Radix Sort Algorithm
Radix sort is a bit more complex to implement than other sorting algorithms such as selection and bubble sort.
It is less flexible than other sorting algorithms as it mostly depends on digits or letters. Therefore, we need to refactor it whenever we need to sort arrays of different data types.
Radix sort is not an in-place sorting algorithm since it requires additional space unlike algorithms such as quicksort, insertion sort, and bubble sort.
Finally, the algorithm can be slower than algorithms that use divide and conquer approaches such as merge sort and quicksort for large arrays.
Performance Tests
Let’s assess how radix sort performs by measuring the time it takes for it to sort an array that has 20,000 elements. To help us complete these tests, we are going to implement three methods.
First, let’s write a method to generate a set of random array elements:
public static int[] CreateRandomArray(int size, int lower, int upper)
{
var array = new int[size];
var rand = new Random();
for (int i = 0; i < size; i++)
array[i] = rand.Next(lower, upper);
return array;
}
The CreateRandomArray() the method takes three integers size, lower and upper. Using the inbuilt Random class, we generate integer values between lower and upper that we’re going to put into the array.
Next, we are going to define a method that generates a sequence of elements. This method simulates an average-case time complexity scenario where the elements are distributed evenly across different digits:
public static int[] CreateSortedArray(int size)
{
var array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i;
return array;
}
To simulate the worst-case time complexity scenario, we are going to use the CreateRandomArray() we have but add an element that has a lot of digits at the end of the array such as Int32.MaxValue:
public static int[] CreateImbalancedArray(int[] array)
{
List<int> numbers = new List<int>();
numbers.AddRange(array);
numbers.Add(Int32.MaxValue);
return numbers.ToArray();
}
Next, we are going to create an object that holds different arrays that have random and sorted values:
public IEnumerable<object[]> SampleArrays()
{
yield return new object[] { CreateRandomArray(20000, 10000, 30000), 20000, "Best Case" };
yield return new object[] { CreateSortedArray(20000), 20000, "Average Case" };
yield return new object[] { CreateImbalancedArray(CreateRandomArray(19999, 10000, 30000)), 20000, "Worst Case" };
}
Each object entry has three values: an integer array e.g. CreateRandomArray(20000, 10000, 30000), its length (20,000), and a string object storing the name of that array (“Best Case”). This object sorts random numbers between 10,000 and 30,000, which have the same number of digits.
The CreateSortedArray() the method creates arrays that have values that are sorted, which is ideal for simulating arrays whose values are uniformly distributed.
On the other hand, the last object invokes the CreateImbalancedArray() which has elements that have elements with the same number of digits except Int32.MaxValue.
Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:
| Method | array | size | arrayName | Mean | Error | StdDev | |---------- |------------- |------ |------------- |---------:|----------:|----------:| | RadixSort | Int32[20000] | 20000 | Average Case | 3.022 ms | 0.0873 ms | 0.2534 ms | | RadixSort | Int32[20000] | 20000 | Best Case | 2.961 ms | 0.0803 ms | 0.2341 ms | | RadixSort | Int32[20000] | 20000 | Worst Case | 7.785 ms | 0.3323 ms | 0.9798 ms |
As we can see, despite the algorithm handling the same number of elements, they have different runtimes, which demonstrates the different levels of time complexities encountered by the array.
The worst-case time complexity’s runtime is about three times longer than the best-case time complexity’s runtime. On the other hand, the average-case runtime is about 1ms slower than the best-case runtime. Please note that these runtimes may change depending on the number of elements and the computing resources available.
Conclusion
In this article, we have learned how radix sort in C# works and its time and space complexity.
