Understanding Radix Sort: Algorithm, Implementation, and Applications in C
Learn Radix Sort, a powerful non-comparative sorting algorithm. Discover its step-by-step logic, C implementation, and practical uses.
Introduction
Sorting algorithms are essential tools in computer science, used to organize data efficiently. Radix Sort is a unique, non-comparative sorting algorithm that sorts data with multiple passes based on individual digits or characters. This blog aims to demystify Radix Sort, offering a thorough understanding of its algorithmic details, a step-by-step explanation, implementation in C, and its time and space complexities. By the end of this blog, you will have a solid grasp of Radix Sort and its practical applications.
Algorithm Details
Radix Sort sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It uses a stable subroutine, such as Counting Sort, to sort the digits.
Step-by-Step Logic
- Find the maximum number: Determine the number with the most digits.
- Sort by each digit: Starting from the least significant digit to the most significant digit, sort the array using Counting Sort as a subroutine.
Pseudo Code
RadixSort(arr):
max_num = getMax(arr)
exp = 1
while max_num / exp > 0:
CountingSort(arr, exp)
exp *= 10
CountingSort(arr, exp):
n = length(arr)
output = array of zeros with length n
count = array of zeros with length 10
for i = 0 to n - 1:
index = (arr[i] // exp) % 10
count[index] += 1
for i = 1 to 9:
count[i] += count[i - 1]
for i = n - 1 downto 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
for i = 0 to n - 1:
arr[i] = output[i]
Explanation of Pseudo Code
- RadixSort(arr):
max_num
identifies the maximum number to determine the number of digits.exp
starts at 1 (least significant digit) and increases by a factor of 10 after each pass.CountingSort
is called for each digit.
- CountingSort(arr, exp):
count
array stores the count of occurrences of each digit (0-9).- The counts are accumulated to determine the positions of each digit.
- The array is sorted based on the current digit and copied back to the original array.
Implementation in C
Here is the implementation of Radix Sort in C.
#include <stdio.h>
// Function to get the maximum value in the array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
// Function to perform counting sort based on the digit represented by exp
void CountingSort(int arr[], int n, int exp) {
int output[n]; // output array
int count[10] = {0};
// Store count of occurrences in count[]
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that count[i] contains the actual position of this digit in output[]
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[], so that arr[] now contains sorted numbers according to the current digit
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
// Main function to do radix sort
void RadixSort(int arr[], int n) {
// Find the maximum number to know the number of digits
int max = getMax(arr, n);
// Do counting sort for every digit. Note that exp is 10^i where i is the current digit number
for (int exp = 1; max / exp > 0; exp *= 10)
CountingSort(arr, n, exp);
}
// Utility function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
RadixSort(arr, n);
printf("Sorted array is: \n");
printArray(arr, n);
return 0;
}
Explanation of C Code
- getMax(int arr[], int n):
- Finds the maximum value in the array to determine the number of digits.
- CountingSort(int arr[], int n, int exp):
- Sorts the array based on the digit represented by
exp
(e.g., units, tens, hundreds). - Initializes the
count
array to store the frequency of each digit. - Accumulates the count to determine the position of each digit.
- Constructs the output array based on the current digit.
- Copies the sorted output array back to the original array.
- Sorts the array based on the digit represented by
- RadixSort(int arr[], int n):
- Calls
CountingSort
for each digit, starting from the least significant digit to the most significant digit.
- Calls
- printArray(int arr[], int n):
- Utility function to print the array.
- main():
- The driver function to test the Radix Sort implementation with a sample array.
Time and Space Complexity
Understanding the complexity of Radix Sort is essential for evaluating its performance.
Time Complexity
- Best, Average, and Worst Case:
O(d * (n + k))
d
is the number of digits in the largest number.n
is the number of elements in the array.k
is the range of the digit (usually 0-9 for decimal numbers).
Space Complexity
- Radix Sort requires additional space for the output array and the counting array.
- Space Complexity:
O(n + k)
Usage of Radix Sort
Radix Sort is particularly useful in scenarios where a stable and efficient sorting algorithm is needed for integers or strings. Common applications include:
- Sorting large datasets of integers: Especially when the range of numbers is large but the number of digits is relatively small.
- String sorting: Can be adapted to sort strings, such as sorting names or dates.
- Data processing: Useful in systems where integer keys need to be sorted quickly.
Conclusion
Radix Sort is a powerful, non-comparative sorting algorithm that provides efficient sorting for integers and strings. Its systematic approach, based on digit-by-digit sorting, ensures a reliable O(d * (n + k))
time complexity. With the detailed explanation, pseudo code, and C implementation provided in this blog, you should now have a solid understanding of Radix Sort and how to implement it in your projects.
By leveraging Radix Sort, you can achieve efficient and stable sorting for various applications, making it an invaluable tool in your programming arsenal. Happy coding!