Radix Sort program in C Language

Radix Sort program in C Language algorithm implementation – Radix sort is a non-comparative sorting algorithm. The Radix sort algorithm is the most preferred algorithm for the unsorted list. Only one element which has significantly large number of digits

Complexity

Table of Contents

Worst case time complexity: O(log_b(mx)(n+b))
Best case time complexity: All elements have the same number of digits
Average case time complexity: O(d(n+b))
Space Complexity: O(n+b)

In this program user would be asked to enter the number of elements along with the element values and then the programs would sort them in ascending order by using merge sorting algorithm logic.

Types of Sorting Algorithms:

Radix Sort algorithm C Program implementation

#include<stdio.h>
int get_max (int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   return max;
}
void radix_sort (int a[], int n){
   int bucket[10][10], bucket_cnt[10];
   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
   lar = get_max (a, n);
   while (lar > 0){
      NOP++;
      lar /= 10;
   }
   for (pass = 0; pass < NOP; pass++){
      for (i = 0; i < 10; i++){
         bucket_cnt[i] = 0;
      }
      for (i = 0; i < n; i++){
         r = (a[i] / divisor) % 10;
         bucket[r][bucket_cnt[r]] = a[i];
         bucket_cnt[r] += 1;
      }
      i = 0;
      for (k = 0; k < 10; k++){
         for (j = 0; j < bucket_cnt[k]; j++){
            a[i] = bucket[k][j];
            i++;
         }
      }
      divisor *= 10;
      printf ("After pass %d : ", pass + 1);
      for (i = 0; i < n; i++)
         printf ("%d ", a[i]);
      printf ("\n");
   }
}
int main (){
   int i, n, a[10];
   printf ("Enter the number of items to be sorted: ");
   scanf ("%d", &n);
   printf ("Enter items: ");
   for (i = 0; i < n; i++){
      scanf ("%d", &a[i]);
   }
   radix_sort (a, n);
   printf ("Sorted items : ");
   for (i = 0; i < n; i++)
      printf ("%d ", a[i]);
   printf ("\n");
   return 0;
}

OUTPUT





Enter number of items to be sorted 6
Enter items:56 78 12 21 56 56
After pass 1 : 12 21 56 56 56 78
After pass 2 : 21 12 56 56 56 78
After pass 3 : 12 21 56 56 56 78
Sorted items : 12 21 56 56 56 78

Additional Reading

you can read more articles like this here.

If you found this post useful, don’t forget to share this with your friends, and if you have any query feel free to comment it in the comment section.❤