Last updated on September 4th, 2023 at 09:43 pm

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

Similar to Counting sort and Bucket sort, Radix Sort is a linear sorting algorithm.

The algorithm based on idea that sorting the elements by first grouping the individual digits of the same place value.

For many programs they need a fast sort, Radix sort is a good choice.

Radix sort depends on the digits or letters, so it is less flexible than other sorts.

1. Take the least significant digit of each element.
2. Sort the list of elements based on that digit, but keep the order of elements with the same digit.
3. Repeat the sort with each more significant digit.

The speed of the Radix sort depends on the inner basic operations.

If the operations are not efficient enough, Radix sort can be slower than other algorithms such as Quick Sort and Merge Sort.

#### Program code in C

``````#include<stdio.h>
//function to get the largest element from an 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;
}
//using counting sort to sort the elements in the basis of significant places
void countingsort(int arr[], int n, int place)
{
int output[n+1];
int max = (arr[0] / place) % 10;

for(int i=1; i<n; i++)
{
if(((arr[i] / place) % 10) > max)
max = arr[i];
}
int count[max+1];
for(int i=0; i<max; i++)
count[i] = 0;
//calculate count of elements
for(int i=0; i<n; i++)
count[(arr[i] / place) % 10]++;
//calculate cummulative count
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--)
{
output[count[(arr[i] / place)% 10] -1] = arr[i];
count[(arr[i] / place)% 10]--;
}
for(int i=0; i<n; i++)
arr[i] = output[i];
}
//main function to implement radix sort
{
//get maximum element
int max = getmax(arr, n);
//apply counting sort to sort elements based on place value
for(int place=1; max/place>0; place*=10)
countingsort(arr, n, place);
}
//print an array
void printarray(int arr[], int n)
{
for(int i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Driver Code
int main()
{
int data[] = {329, 457, 657, 839, 436, 720, 355};
int size = sizeof(data)/sizeof(data[0]);
printf("Sorted array : ");
printarray(data, size);
}```Code language: C++ (cpp)```

#### Output

``Sorted array : 329 355 436 457 657 720 839`Code language: PHP (php)`

1. Fast when the keys are short i.e when the range of the array elements is less.
2. Used in suffix array construction algorithms like Manber’s algorithm and DC3 algorithm.

1. Radix Sort depends on digits or letters, so it is less flexible than other sorts.
2. The constant for Radix sort is greater compared to other sorting algorithms.
3. It takes more space compared to Quick sort which is inplace sorting.