In this tutorial, you'll find out how radix sorting works. you'll also find working samples of radix sort in C, C ++, Java, and Python.

Radix sorting use to sorts the items by first grouping the individual digits of equivalent place value. Then sort the things in ascending / descending order.

Suppose we have got an array of 8 elements. First, we'll sort the things that supported the worth of the unit square. Next, we'll sort the things that supported the worth of the tenth place. This process continues until the last significant place.

Let be the initial table [121, 432, 564, 23, 1, 45, 788]. it's sorted consistent with the essential sort as shown within the figure below.

radix sort in c program

How does the Radix sort algorithm work?

•  Find the most important element within the array, i.e. max. Let X be the number of digits in max. X is calculated because we've to travel through all the many places in all the weather.

 during this table [121, 432, 564, 23, 1, 45, 788], we've the most important number 788. it's 3 digits. Therefore, the loop must go up to many places (3 times).

•  Now undergo each significant spot one by one.

radix sort in c

 Use any stable sorting technique to sort the digits at each significant place. We used the count sort for this.

 Sort the things supported the unit's location digits (X = 0).

• Now sort the things supported the ten numbers.

radix sort in the data structure

• Finally, sort the things by numbers with the hundredth place of giving number.

Redix Sort Algorithm at the hundredth place

Time complexity of radix sort

Since the radix sort Algorithm is a non-comparative algorithm, its advantages over comparative sorting algorithms.

• For basic sort which uses count sort as an intermediate stable sort, the time complexity is O (d (n + k)).

• Here, d is that the cycle of numbers and O (n + k) is that the time complexity of the counting sort.

• Thus, radix sorting has linear time complexity which is best than O (nlog n) of comparative sorting algorithms.

• If we take very large numbers of digits or the amount of other bases like 32-bit and 64-bit numbers, then it can add linear time, but the intermediate sort takes up tons of space.

• This makes the essential sorting space inefficient. this is often the rationale why this type isn't utilized in software libraries.

Redix Sort program in C

#include <stdio.h> 

 int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}


void countingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((array[i] / place) % 10) > max)
      max = array[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0; 

 for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++; 

 for (int i = 1; i < 10; i++)
    count[i] += count[i - 1]; 

 for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
} 

 void radixsort(int array[], int size) {
  // Get maximum element
  int max = getMax(array, size);

  // Apply counting sort to sort elements based on place value.
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
} 

 void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
} 

 int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  printArray(array, n);
}

Applications For Radix sort Algorithm

Radix sorting is implemented in

•  DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while creating an array of suffixes.

•  places where there are numbers in large ranges.