Radix Sort

Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.

Suppose, we have an array of 8 elements. First, we will sort elements based on the value of the unit place. Then, we will sort elements based on the value of the tenth place. This process goes on until the last significant place.

Working :

Find the largest element in the array, i.e. max. Let X be the number of digits in max. X is calculated because we have to go through all the significant places of all elements.
Now, go through each significant place one by one.
Use any stable sorting technique to sort the digits at each significant place. We have used counting sort for this.
Sort the elements based on the unit place digits (X=0).
Now, sort the elements based on digits at tens place.
Finally, sort the elements based on the digits at hundreds place.

Algorithm

    radixSort(arr)  
    max = largest element in the given array  
    d = number of digits in the largest element (or, max)  
    Now, create d buckets of size 0 - 9  
    for i -> 0 to d  
    sort the array elements using counting sort (or any stable sort)
    according to the digits at the ith place

Program using C

//RADIX SORT
#include <stdio.h>  
  
    int getMax(int a[], int n) {  
       int max = a[0];  
       for(int i = 1; i<n; i++) {  
          if(a[i] > max)  
             max = a[i];  
       }  
       return max; //maximum element from the array  
    }  
      
    void countingSort(int a[], int n, int place) // function to implement counting sort  
    {  
      int output[n + 1];  
      int count[10] = {0};    
      
      // Calculate count of elements  
      for (int i = 0; i < n; i++)  
        count[(a[i] / place) % 10]++;  
          
      // Calculate cumulative frequency  
      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[(a[i] / place) % 10] - 1] = a[i];  
        count[(a[i] / place) % 10]--;  
      }  
      
      for (int i = 0; i < n; i++)  
        a[i] = output[i];  
    }  
      
    // function to implement radix sort  
    void radixsort(int a[], int n) {  
       
      // get maximum element from array  
      int max = getMax(a, n);  
      
      // Apply counting sort to sort elements based on place value  
      for (int place = 1; max / place > 0; place *= 10)  
        countingSort(a, n, place);  
    }  
      
    // function to print array elements  
    void printArray(int a[], int n) {  
      for (int i = 0; i < n; ++i) {  
        printf("%d  ", a[i]);  
      }  
      printf("\n");  
    }  
      
    int main() {  
      int a[] = {181, 289, 390, 121, 145, 736, 514, 888, 122};  
      int n = sizeof(a) / sizeof(a[0]);  
      printf("Before sorting array elements are - \n");  
      printArray(a,n);  
      radixsort(a, n);  
      printf("After applying Radix sort, the array elements are - \n");  
      printArray(a, n);  
    }