In this article, we will learn about what is radix sort program, the algorithm of the radix sort program, how the radix sort program works with a dry-run of an example, and the radix sort program in c with an example.
What is radix sort?
Radix sort is used to sort arrays of type integer only and it is a linear sorting algorithm. In this algorithm, the array is sorted digit by digit. Sorting is performed on the least significant digit to the most significant digit. Let’s see what is the least significant digit and what is the most significant digit by an example.
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.
Other C Programs
C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C
Doubly Linked List Program in C
FCFS Scheduling Program in C
Insertion Sort Program in C
Singly Linked List Program in C
Star Program in C
String Program in C