Last Updated on June 8, 2023 by Mayank Dham
In this article, we will learn what is radix sort program in C, its algorithm, how it operates with a dry-run example, and how to implement a radix sort program in C with an example.
What is radix sort?
Radix sort is a linear sorting method that is exclusively used to sort arrays of the integer data type. The array is sorted in this algorithm digit by digit. The least significant digit to the most significant digit is sorted. Let’s use an example to illustrate which digit is the least important and which is the most important.
From the above picture, we will do a sorting from the last significant digit 4 to the most significant digit 7. Thus, in the first pass, we will sort all the elements of the array by the least significant array. After that, we will move toward the most significant digit, digit by digit, and sort the array. Now, let’s see the algorithm of the radix sort.
Algorithm of the Radix sort:
Below is the algorithm for the Radix sort.
radix_sort(arr)
max_element = largest element in the given array
digits = number of digits in max_element
Create total digit buckets of size 0 - 9
for i -> 0 to digits
sort the array elements using counting sort (or any stable sort) according to the digits at the ith place
main()
radix_sort(arr)Working of the Radix sort with dry-run:
Let’s see how the Radix sort algorithm works using an example. First, we will see some steps to perform the Radix sort algorithm.
- Find the maximum element in the array and store it in max_element.
- Calculate the total digits in that max_element and store it in digits.
- Now we need to run through all the digits of max_elemnt.
- We will go through each digit from the least significant digit to the most significant digit and sort it.
Now, let’s see how the Radix sort algorithm works. We will take an example and do a dry run as well to understand the working of an algorithm.
We have taken an array of random integers. First, we will find the maximum element in the array which is 954. The maximum element 954 has 3 digits thus the loop will run 3 times and we have to go through 3 passes to sort an array. We will start from the least significant digit ( digit at place 0) to the most significant digit ( digit at place 2).
First Pass:
In the first pass, we will sort an array based on the least significant digit ( digit at 0th place).
In the above picture, we can see that we have stored elements in another array of size 10 based on the least significant digit. After that, we will again transfer all the elements to the original array. Now, our array will look like this:
We will consider the above array for the second pass.
Second Pass:
In the second pass, we will sort an array based on the second least significant digit ( digit at 1st place ).
In the above picture, we can see that we have stored elements in another array based on the second least significant digit ( digit at 1st place ). After that, we will again transfer all the elements to the original array. Now, our array will look like this:
We will consider the above array for the third pass.
Third Pass:
In the second pass, we will sort an array based on the most significant digit ( digit at 2nd place ).
In the above picture, we can see that we have stored elements in another array based on the most significant digit ( digit at 2nd place ). After that, we will again transfer all the elements to the original array. Now, our array will look like this:
After the completion of the third pass, we can see that now our array is sorted.
C Program Code of Radix Sort
Now, we have a pretty good idea about how the radix sort algorithm works. Let’s see how to write the radix sort program in c. We will use the counting sort method to implement the radix sort program in c. Counting sort means we will count the numbers having the same digit as the given position and we will store it accordingly. Now, we will write the radix sort program in c.
//radix sort program in c
#include <stdio.h>
// function to get maximum element from array
int find_max(int arr[], int n) {
int max_element = arr[0];
for(int i = 1; i<n; i++) {
if(arr[i] > max_element)
max_element = arr[i];
}
return max_element;
}
void countingSort(int arr[], int n, int pos)
{
int result[n + 1];
int count[10] = {0};
// count howmany numbers are present with digit 0-9 at given position
for (int i = 0; i < n; i++)
count[(arr[i] / pos) % 10]++;
// now do prefix sum of the count array
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = n - 1; i >= 0; i--) {
result[count[(arr[i] / pos) % 10] - 1] = arr[i];
count[(arr[i] / pos) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = result[i];
}
void radixsort(int arr[], int n) {
int max_element = find_max(arr, n);
// counting sort from the least significant digit to the most significant digit
for (int pos = 1; max_element / pos > 0; pos *= 10)
countingSort(arr, n, pos);
}
int main() {
int arr[] = {312, 42, 635, 11, 8, 783, 954, 777};
int n = sizeof(arr) / sizeof(arr[0]);
printf("An array before applying the radix sort: \n");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
radixsort(arr, n);
printf("An array after applying the radix sort: \n");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
} Output
An array before applying the radix sort:
312 42 635 11 8 783 954 777
An array after applying the radix sort:
8 11 42 312 635 777 783 954 In the above radix sort program in c, We have created the function radixSort in which first, we will find the maximum of the array using the find_max function. After that, we will run a loop from 0 to the total number of a digit in max_element. During each loop, we will sort the array based on the given position using counting sort. In the counting sort function, we will create an array result to store the result after performing the sorting to a particular position. After that, we will count how many elements are present in the array from 0-9 at a given position and store it in the desired position. After that, we will place all the elements in the result array based on sorting. In the end, we will assign all the elements from the result array to the original array arr. Now, let’s see what is the time complexity of the radix sort program in c and the space complexity of
C program of the radix sort.
*Time Complexity: O(nd)* where n is the size of an array and d is the number of digits in the largest element of the array. In the worst case, we might end up sorting the array in each loop. Thus the time complexity of the radix sort program in c is O(nd).
Space Complexity: O(n+d) because we are using extra arrays to store results and count.
Note: Radix sort is stable because after performing the sorting still the order of the element is maintained. Radix sort is not in-place because we are using extra space to sort the array.
Conclusion
In conclusion, Radix Sort is a non-comparative sorting algorithm that efficiently sorts integers by examining the digits or characters at different positions. It has a linear time complexity, making it an excellent choice for sorting large datasets with a fixed number of digits. By using a stable sorting algorithm as a subroutine, Radix Sort can achieve overall stability. The algorithm works by repeatedly sorting the elements based on their individual digits or characters, from the least significant position to the most significant position. Radix Sort is widely used in computer science and is particularly useful when dealing with large integers or strings.
Frequently Asked Questions (FAQs):
Q1: What is Radix Sort?
Radix Sort is a non-comparative sorting algorithm that sorts integers or strings based on their individual digits or characters at different positions. It achieves sorting by repeatedly sorting the elements according to their digits or characters from the least significant position to the most significant position.
Q2: How does Radix Sort work?
Radix Sort works by distributing the elements into different buckets or queues based on the values of their digits or characters at a particular position. After sorting the elements based on a specific digit or character, it gathers them back into a single sequence. This process is repeated for each digit or character position, resulting in a fully sorted sequence.
Q3: What is the time complexity of Radix Sort?
The time complexity of Radix Sort is O(kN), where N is the number of elements to be sorted, and k is the number of digits or characters in the largest element. Since k is considered a constant factor, Radix Sort is often regarded as having linear time complexity, making it efficient for sorting large datasets.
Q4: Is Radix Sort a stable sorting algorithm?
Yes, Radix Sort can be made stable by using a stable sorting algorithm as a subroutine when sorting the elements based on each digit or character. By maintaining the relative order of elements with the same digit or character value, Radix Sort achieves overall stability.
Q5: In which scenarios is Radix Sort useful?
Radix Sort is particularly useful when sorting large integers or strings with a fixed number of digits or characters. It is often employed in scenarios where a high-speed sorting algorithm is required and the range of possible values is known or limited. Examples include sorting student IDs, IP addresses, or fixed-length numeric representations.