  Written by Shuvhojit DebFebruary 3, 2022
C
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE Shuvhojit Deb

Full Stack Developer

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

Using counting sort to sort elements based on unit place

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

Sort elements based on tens place

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

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;`
`   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, bucket_cnt;`
`   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;`
`   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
Software
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE     You must be Logged in to comment
Code Block Shuvhojit Deb
Full Stack Developer  117 Blog Posts
Trending Technologies
15 Software40 DevOps46 Frontend Development24 Backend Development20 Server Administration17 Linux Administration26 Data Center24 Sentry24 Terraform23 Ansible83 Docker70 Penetration Testing16 Kubernetes21 NGINX20 JenkinsX17
Recommended Blogs
8        8 Anik Adhikary Anik Adhikary Anik Adhikary Anik Adhikary Anik Adhikary Anik Adhikary Anik Adhikary Anik Adhikary 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.