Sorting is a fundamental concept in programming, and Radix Sort offers an efficient way to sort numbers. Unlike comparison-based algorithms, Radix Sort works by processing each digit of the numbers individually, usually starting from the least significant digit to the most significant. This makes it very fast for sorting large datasets of integers, especially when the number of digits is relatively small.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is widely used in applications like digital systems, data processing, and computer graphics, where speed matters more than the simplicity of the code. Learning Radix Sort in C# helps beginners understand non-comparison-based sorting and provides a clear view of how to manipulate arrays and lists efficiently. By using predefined data in examples, learners can easily follow the sorting steps and see how the algorithm organizes data incrementally.
Program 1: Radix Sort Using Arrays
This program demonstrates the standard Radix Sort using arrays to sort integers in ascending order. It processes each digit of the numbers using a counting sort internally.
using System;
class Program
{
static int GetMax(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
static void CountingSort(int[] arr, int exp)
{
int n = arr.Length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
{
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
static void RadixSort(int[] arr)
{
int max = GetMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10)
CountingSort(arr, exp);
}
static void Main()
{
int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
RadixSort(arr);
Console.WriteLine("Sorted array:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}In this program, each digit of the numbers is processed using a stable counting sort, ensuring that the order of numbers with the same digit remains consistent. Beginners can see how the algorithm builds up a sorted array digit by digit, which is different from traditional comparison-based sorts.
Program 2: Radix Sort With Negative Numbers
Radix Sort typically handles positive numbers. This program shows how to extend it to sort arrays containing negative numbers by separating positives and negatives.
using System;
using System.Collections.Generic;
class Program
{
static void RadixSort(int[] arr)
{
List<int> pos = new List<int>();
List<int> neg = new List<int>();
foreach (int num in arr)
if (num >= 0)
pos.Add(num);
else
neg.Add(-num);
SortList(pos);
SortList(neg);
neg.Reverse();
int index = 0;
foreach (int num in neg)
arr[index++] = -num;
foreach (int num in pos)
arr[index++] = num;
}
static void SortList(List<int> list)
{
if (list.Count == 0) return;
int max = list[0];
foreach (int num in list)
if (num > max) max = num;
int exp = 1;
while (max / exp > 0)
{
CountingSort(list, exp);
exp *= 10;
}
}
static void CountingSort(List<int> list, int exp)
{
int n = list.Count;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(list[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
{
int index = (list[i] / exp) % 10;
output[count[index] - 1] = list[i];
count[index]--;
}
for (int i = 0; i < n; i++)
list[i] = output[i];
}
static void Main()
{
int[] arr = { 170, -45, 75, -90, 802, 24, 2, -66 };
RadixSort(arr);
Console.WriteLine("Sorted array with negative numbers:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This program separates positive and negative numbers, sorts them independently, and then merges them back. Beginners can understand how simple adjustments allow Radix Sort to handle more complex data.
Program 3: Radix Sort With Strings
Radix Sort can also sort strings of equal length, such as sorting names or codes alphabetically.
using System;
class Program
{
static void RadixSort(string[] arr)
{
int n = arr.Length;
int maxLen = arr[0].Length;
foreach (string str in arr)
if (str.Length > maxLen) maxLen = str.Length;
for (int pos = maxLen - 1; pos >= 0; pos--)
{
int[] count = new int[256];
string[] output = new string[n];
for (int i = 0; i < n; i++)
{
char ch = pos < arr[i].Length ? arr[i][pos] : '\0';
count[ch]++;
}
for (int i = 1; i < 256; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
{
char ch = pos < arr[i].Length ? arr[i][pos] : '\0';
output[count[ch] - 1] = arr[i];
count[ch]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
}
static void Main()
{
string[] arr = { "Banana", "Apple", "Mango", "Orange" };
RadixSort(arr);
Console.WriteLine("Sorted string array:");
foreach (string str in arr)
Console.Write(str + " ");
Console.WriteLine();
}
}By treating each character as a digit, this variation demonstrates Radix Sort’s adaptability. Beginners can see how the algorithm generalizes beyond numbers.
Program 4: Radix Sort With Large Numbers
Radix Sort is especially efficient for large numbers, since it doesn’t require pairwise comparisons.
using System;
class Program
{
static void RadixSort(long[] arr)
{
long max = arr[0];
foreach (long num in arr)
if (num > max) max = num;
for (long exp = 1; max / exp > 0; exp *= 10)
CountingSort(arr, exp);
}
static void CountingSort(long[] arr, long exp)
{
int n = arr.Length;
long[] output = new long[n];
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(int)((arr[i] / exp) % 10)]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
{
int index = (int)((arr[i] / exp) % 10);
output[count[index] - 1] = arr[i];
count[index]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
static void Main()
{
long[] arr = { 123456789012, 987654321098, 123456789, 9876543210 };
RadixSort(arr);
Console.WriteLine("Sorted large numbers:");
foreach (long num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This example shows Radix Sort’s efficiency with large datasets, as it scales linearly with the number of digits rather than the number of elements squared.
Frequently Asked Questions (FAQ)
Q1: What is Radix Sort?
Radix Sort is a non-comparison-based sorting algorithm that processes each digit of numbers to sort arrays efficiently.
Q2: Can Radix Sort handle negative numbers?
Yes, by separating positive and negative numbers and sorting them independently, Radix Sort can handle negative values.
Q3: Is Radix Sort faster than Quick Sort?
For large arrays with integers or fixed-length strings, Radix Sort can be faster since its time complexity is O(n × k), where k is the number of digits.
Q4: Can Radix Sort sort strings?
Yes, by treating characters as digits, Radix Sort can sort fixed-length strings alphabetically.
Q5: Is Radix Sort stable?
Yes, Radix Sort is stable, meaning it preserves the relative order of elements with the same value.
Conclusion
Radix Sort is a versatile and efficient sorting algorithm that is especially useful for numbers and strings. By processing digits individually and using stable sub-sorts, it can handle large datasets faster than traditional comparison-based algorithms. Practicing Radix Sort in C# helps beginners understand non-comparison sorting, stable algorithms, and array manipulation. Exploring variations like negative numbers, strings, and large numbers makes the algorithm practical for real-world applications and strengthens a programmer’s problem-solving skills.
