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;
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 / 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);
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.

### Time and Space Complexity of Radix Sort

1. DC3 algorithm while making a suffix array.
2. places where there are numbers in large ranges.

### Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …

### Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …

### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …

### Shell Sort

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

### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …

### Bucket Sort

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

### Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders. 