Radix sort is a linear sorting algorithm for integers and uses the concept of sorting names in alphabetical order. When we have a list of sorted names, the radix is 26 (or 26 buckets) because there are 26 letters in the English alphabet. So radix sort is also known as bucket sort.

In radix sort, words are first sorted according to the first letter of the name. That is, 26 classes are used to arrange the names, where the first class stores the names that begin with A, the second class contains the names with B, and so on.

During the second pass, names are grouped according to the second letter. After the second pass, names are sorted on the first two letters. This process is continued till the nth pass, where n is the length of the name with the maximum number of letters.

After every pass, all the names are collected in order of buckets. That is, first pick up the names in the first bucket that contains the names beginning with A. In the second pass, collect the names from the second bucket, and so on.

When radix sort is used on integers, sorting is done on each of the digits in the number. The sorting procedure proceeds by sorting the least significant to the most significant digit. While sorting the numbers, we have ten buckets, each for one digit (0, 1, 2, …, 9) and the number of passes will depend on the length of the number having the maximum number of digits.

Radix sort can be done into two ways:

  1. LSD radix sort
    • Least-significant-digit-first radix sort.
    • LSD(Most Significant Digit) radix sort first sorts the integers based on the least significant digits and then proceeds sorting for most significant digits . So, there is no problem if the keys are of non-equal length because of the reason that MSD has more weight-age.

  2. MSD radix sort
    • Most-significant-digit-first radix sort.
    • MSD(Most Significant Digit) radix sort starts with most significant digits and then proceeds sorting to least significant digits , if the given keys are of unequal length , we have to place required number of 0's infront of them to make equal length. Then only we can sort based on most significant digits .

LSD first sorts least significant digits and then sorts the keys with same length in lexicographical order

MSD sorts the keys in lexicographical order.

LSD is faster than MSD when there is a fixed length. MSD is too slow for small files, and it need huge number of recursive calls on small files.

radix-sort-algorithm-example-min.png

In the above example you can see, in the first pass, the numbers are sorted according to the digit at two's place.

After this pass, the numbers are collected bucket by bucket. The new list thus formed is used as an input for the next pass. In the second pass, the numbers are sorted according to the digit at the ones place.

The numbers are collected bucket by bucket. The new list thus formed is the final sorted result.

Radix sort algorithm

Step 1: Find the largest number in ARR as LARGE
Step 2: [INITIALIZE] SET NOP = Number of digits in LARGE
Step 3: SET PASS = 0
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5:         SET I= and INITIALIZE buckets
Step 6:         Repeat Steps 7 to 9 while I<N-1
Step 7:               SET DIGIT = digit at PASSth place in A[I]
Step 8:               Add A[I] to the bucket numbered DIGIT
Step 9:               INCEREMENT bucket count for bucket numbered DIGIT
                [END OF LOOP]
Step 10:        Collect the numbers in the bucket
        [END OF LOOP]
Step 11: END

Complexity of radix sort

To calculate the complexity of radix sort algorithm, assume that there are n numbers that have to be sorted and k is the number of digits in the largest number. In this case, the radix sort algorithm is called a total of k times. The inner loop is executed n times.

Hence, the entire radix sort algorithm takes O(kn) time to execute. When radix sort is applied on a data set of finite size (very small set of numbers), then the algorithm runs in O(n) asymptotic time.

Radix Sort C program code

#include <stdio.h> 
#include <conio.h> 

#define size 10

int largest(int arr[], int n);
void radix_sort(int arr[], int n);

void main() {
  int arr[size], i, n;
  //enter the numbers of elements in array
  printf("\n Enter the number of elements in the array: ");
  scanf("%d", &n);
  
  //enter array elements
  printf("\n Enter the elements of the array: ");
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
   //call the radix sort function
  radix_sort(arr, n);
  
  
  printf("\n The sorted array is: \n");
  for (i = 0; i < n; i++)
  {
    printf(" %d\t", arr[i]);
  }
  
}

//funtion to find largest element
int largest(int arr[], int n) {
  int large = arr[0], i;
  for (i = 1; i < n; i++) {
    if (arr[i] > large)
      large = arr[i];
  }
  return large;
}


//radix sort function, takes array data and count of elements
void radix_sort(int arr[], int n) {
  int bucket[size][size], bucket_count[size];
  int i, j, k, remainder, NOP = 0, divisor = 1, large, pass;
  large = largest(arr, n);
  while (large > 0) {
    NOP++;
    large /= size;
  }
  for (pass = 0; pass < NOP; pass++) // Initialize the buckets
  {
    for (i = 0; i < size; i++)
      bucket_count[i] = 0;
    for (i = 0; i < n; i++) {
      // sort the numbers according to the digit at passth place
      remainder = (arr[i] / divisor) % size;
      bucket[remainder][bucket_count[remainder]] = arr[i];
      bucket_count[remainder] += 1;
    }
    // collect the numbers after Nth PASS pass
    i = 0;
    for (k = 0; k < size; k++) {
      for (j = 0; j < bucket_count[k]; j++) {
        arr[i] = bucket[k][j];
        i++;
      }
    }
    divisor *= size;
  }
}

Output after executing program online https://onlinegdb.com/Hk7ykOS-X

 Enter the number of elements in the array: 5

 Enter the elements of the array: 22 89 5 6 11

 The sorted array is: 
 5	 6	 11	 22	 89

radix-sort-program-in-c-min.png

You may also like:

Selection sort program in C (With Algorithm)

Merge sort algorithm in C with Program sample

Bubble sort algorithm in C (With sample program)

Pros/Cons of Radix sort

  • Radix sort is a very simple algorithm.
  • When programmed properly, radix sort is one of the fastest sorting algorithms for numbers or strings of letters.
  • Drawback of radix sort is that the algorithm is dependent on digits or letters. This feature compromises with the flexibility to sort input of any data type. For every different data type, the algorithm has to be rewritten.
  • Radix sort takes more space than other sorting algorithms. Besides the array of numbers, we need 10 buckets to sort numbers, 26 buckets to sort strings containing only characters, and at least 40 buckets to sort a string containing alphanumeric characters
  • Radix sort is a good choice for many programs that need a fast sort, but there are faster sorting algorithms available. This is the main reason why radix sort is not as widely used as other sorting algorithms.