Radix Sort

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.

What is Radix Sort?

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.

Radix Sort Algorithm

  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.

Radix Sort
RADIX SORT

Implementation of Radix 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
void radixsort(int arr[], int n)
{
  //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]);
  radixsort(data, size);
  printf("Sorted array : ");
  printarray(data, size);
}

Output

Sorted array : 329 355 436 457 657 720 839

Advantages of Radix Sort

  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.

Disadvantages of Radix Sort

  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

Time Complexity
Worst CaseO(nk)
Best CaseO(nk)
Average CaseO(nk)
Space Complexity
Worst CaseO(n+k)

Applications of Radix Sort

Radix sort is implemented in

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

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎

Scroll to Top