Hello! Today we will explore the concept of Radix Sort and how to implement it using C#. Radix Sort is one of the efficient ways to sort unsorted data, particularly useful when the range of integers is limited.
1. What is Radix Sort?
Radix Sort is a method of sorting numbers based on the position of their digits, typically divided into LSD (Least Significant Digit) and MSD (Most Significant Digit) methods. Using L starts the sorting from the lowest digit, while starting with M sorts from the highest digit.
2. How Radix Sort Works
The mechanism of Radix Sort works as follows:
- Starting from the least significant digit, sort the data based on each digit.
- Repeat the sorting process up to the most significant digit.
- In this process, a stable sorting algorithm, such as Counting Sort, is used to sort based on each digit.
3. Time Complexity of Radix Sort
The time complexity of Radix Sort is O(d * (n + k)), where d is the number of digits in the numbers, n is the number of integers to sort, and k is the range of digits from 0 to the maximum digit. One of the biggest advantages is that Radix Sort is stable.
4. Example Problem Solving with Radix Sort
Now, let’s solve a problem by sorting a specific list of numbers using Radix Sort.
Problem Description
Sort the given list of integers in ascending order using Radix Sort.
Input: [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Problem Solving Process
- Start from the least significant digit. Sort using the first digit in the units place.
C#
public static void LSDRadixSort(int[] array)
{
// Find the largest number.
int max = array.Max();
// Find the number of digits.
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, exp);
}
}
private static void CountingSort(int[] array, int exp)
{
int n = array.Length;
int[] output = new int[n]; // Sorted array
int[] count = new int[10]; // Count for digits 0-9
// Count the number of elements corresponding to the digit.
for (int i = 0; i < n; i++)
{
count[(array[i] / exp) % 10]++;
}
// Calculate cumulative count.
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
// Create the sorted array.
for (int i = n - 1; i >= 0; i--)
{
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
// Update the original array.
for (int i = 0; i < n; i++)
{
array[i] = output[i];
}
}
In the above code, we define the LSDRadixSort method. This method sorts using CountingSort for each digit.
5. Implementation and Execution
Now, we will run the entire program using the above functions. Below is the complete code for the program:
C#
using System;
using System.Linq;
class Program
{
public static void Main(string[] args)
{
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
LSDRadixSort(array);
Console.WriteLine("Sorted array:");
Console.WriteLine(string.Join(", ", array));
}
public static void LSDRadixSort(int[] array)
{
int max = array.Max();
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, exp);
}
}
private static void CountingSort(int[] array, int exp)
{
int n = array.Length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
{
count[(array[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--)
{
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
{
array[i] = output[i];
}
}
}
When executing the above code, the following results can be obtained:
Sorted array:
2, 24, 45, 66, 75, 90, 170, 802
6. Advantages and Disadvantages of Radix Sort
The advantages of Radix Sort are as follows:
- Fast speed: Excellent performance under certain conditions. (i.e., when the range is limited)
- Stable sort: Maintains relative order of equivalent values.
However, there are also disadvantages:
- Memory usage: Requires additional memory.
- Limited data: Difficult to use for data types other than integers.
7. Conclusion
Today, we examined the basic concept of Radix Sort, its operation principle, time complexity, and problem examples. This algorithm is very useful for efficiently handling collections that contain integers. It is also good to try Radix Sort during actual coding tests.
See you in the next lecture! Good luck with your coding test preparation!