Written by **Shuvhojit Deb**February 3, 2022

10 min read

C

Full Stack Developer

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.

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.

**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

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

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

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

Was this blog helpful?

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

Recommended Threads

8

Anik Adhikary

Anik Adhikary

Anik Adhikary