Radix Sort in C

Radix Sort in C
Techiio-author
Written by Shuvhojit DebFebruary 3, 2022
10 min read
C
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE
Techiio-author
Shuvhojit Deb

Full Stack Developer

In this article, we'll learn what radix sort in C is.

What is Radix Sort in C Program?

Radix sort is a non-comparative sorting algorithm used for a variety of digit manipulation activities in any computer language. Radix sort seeks to avoid putting a large number of distributed elements into a bucket to sort the elements in the bucket according to the radix and index within it for a large number of digits. Radix sort in C is also known as Bucket sort of digital sort since it is concerned with preserving order and number. Radix sort is used on data that has already been sorted lexically.

Syntax

Radix sort in C don’t have any particular format but have some syntax that is used for representation according to the requirement, which is as follows:

  • Take an unsorted list in C.
  • Sort in the list using the least significant digit, which provides the following values.
  • Then find the next significant bit of the digit, i.e., in 10th place, which alters the value when compared with the previous list.
  • Then start sorting using the next most significant digit in 100th place, which gives the following values within the list.

How Radix Sort Works in C Program?

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 of places (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).

blogpost

Using counting sort to sort elements based on unit place

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

blogpost

Sort elements based on tens place

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

blogpost

Sort elements based on hundreds place

Algorithm

Radix_sort (list, n)
shift = 1
for loop = 1 to keysize do
   for entry = 1 to n do
   bucketnumber = (list[entry].key / shift) mod 10
   append (bucket[bucketnumber], list[entry])
list = combinebuckets()
shift = shift * 10

Example:

This program demonstrates the implementation of Radix sort in C, as shown in the output.

#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:567 789 121 212 563 562
After pass 1 : 121 212 562 563 567 789
After pass 2 : 212 121 562 563 567 789
After pass 3 : 121 212 562 563 567 789
Sorted items : 121 212 562 563 567 789

Conclusion

Radix sort, due to its efficient and faster computational value in terms of digits and orders, is really useful nowadays wherever any sorting algorithm is involved. It is used for making the entire sorting paradigm for implementation easy and flexible. LSD and MSD sorting involved makes the traversal and operations smoother and clean.

C Language
C Programming
Radix Sort
Software
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE
Was this blog helpful?
techiio-price-plantechiio-price-plantechiio-price-plantechiio-price-plantechiio-price-plan
You must be Logged in to comment
Code Block
Techiio-logo

Techiio is on the journey to build an ocean of technical knowledge, scouring the emerging stars in process and proffering them to the corporate world.

Follow us on:

Subscribe to get latest updates

You can unsubscribe anytime from getting updates from us
Developed and maintained by Wikiance
Developed and maintained by Wikiance