Radix Sort Algorithm in C language

Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of same place. Radix sort uses counting sort as a subroutine to sort. The Radix Sort Algorithm.

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.

Let the initial array be [121, 432, 564, 23, 1, 45, 788]. It is sorted according to radix sort as shown in the figure below.

 Customer Reviews: 4.4 out of 5 stars170 customer ratings

Please go through the counting sort before reading this article because counting sort is used as an intermediate sort in radix sort.

---

How Radix Sort Works?

1. 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.
   
   In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788. It has 3 digits. Therefore, the loop should go up to hundreds place (3 times).
2. 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).
   

   

3. Now, sort the elements based on digits at tens place.
   

   

4. Finally, sort the elements based on the digits at hundreds place.
   

   

// Radix Sort in C Programming


#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)

{

  int max = getMax(array, size);


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

}


Visit Our Channel for Similar tutorials

Data Structures Examples

Learn SEO Tips and Digital Marketing