Radix Sort is a non-comparative sorting algorithm that sorts elements based on the number of digits (or characters) and the values of individual digits (or characters) in a list. It is a stable sorting algorithm and performs well when dealing with large lists of integers with many digits.
Radix Sort is particularly useful for sorting large integers or strings with fixed-length digits (or characters). It avoids the need for comparisons between elements, which can lead to improved performance compared to other sorting algorithms like QuickSort or MergeSort.
Radix Sort works by iteratively sorting the elements according to the number of significant digits (or characters) from right to left. In each iteration, we sort the elements based on the values of the current significant digit (or character).
In this guide, we will focus on the implementation of Radix Sort in C. We will walk through a step-by-step example of sorting an array of integers.
Consider an array arr[] with the following elements:
int arr[] = {170, 45, 75, 90, 802, 24, 2, 36};First, we find the maximum value in the array and determine the number of digits (or characters) required to represent the maximum value.
#include <stdio.h>
#define SIZE 8
int maxValue(int arr[], int size) {
int max = arr[0];
for (int i = 1; i < size; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
int maxDigits(int max) {
int digits = 0;
while (max > 0) {
max /= 10;
digits++;
}
return digits;
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}Next, we create sub-arrays for each digit (or character) to store the elements that have the same value at that position. This step is repeated for each digit (or character) from right to left.
void countSort(int arr[], int size, int digit, int output[]) {
int count[10] = {0};
int outputArray[SIZE];
for (int i = 0; i < size; i++) {
int index = (arr[i] / (int)pow(10, digit)) % 10;
count[index]++;
}
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = 0; i < size; i++) {
int index = (arr[i] / (int)pow(10, digit)) % 10;
outputArray[count[index] - 1] = arr[i];
count[index]--;
}
for (int i = 0; i < size; i++)
arr[i] = outputArray[i];
}Finally, we iterate through the digits (or characters) and perform the count sorting step. After each iteration, the array will be sorted based on the values of the current significant digit (or character).
void radixSort(int arr[], int size) {
int max = maxValue(arr, size);
int digits = maxDigits(max);
for (int digit = 1; digit <= digits; digit++) {
countSort(arr, size, digit, NULL);
}
}With all the pieces in place, we can now sort our example array.
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 36};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original Array:\n");
printArray(arr, size);
radixSort(arr, size);
printf("Sorted Array:\n");
printArray(arr, size);
return 0;
}Radix Sort has practical applications in various areas such as database management systems, data compression, and computer graphics. Its efficiency makes it a valuable tool for dealing with large datasets and large integers.
In this guide, we have explored C Radix Sort and learned how to implement it for sorting an array of integers. The algorithm offers a stable sort and performs well when dealing with large integers with many digits. By understanding the concept and implementation, you can apply Radix Sort to real-world projects and improve your problem-solving skills.
Which of the following statements is true about Radix Sort?
What is the maximum number of iterations in the C Radix Sort implementation provided in this guide?