Write a C Program to Implement Radix Sort.

**Radix sort** is a sorting technique. Here in **radix sort**, instead of comparing the elements with each other and placing them in their right order, we sort these elements in the collection digit by digit moving from Least significant bit to Most significant bit while preserving their previous state/order.

We can preserve their order by using a stable sorting method such as **count sort**.

**Example:** (Working of radix sort)

Let’s say we have this array, containing 7 elements. Name of this array is **arr**.

256 | 055 | 047 | 123 | 807 | 121 | 009 |

**arr [7]** = {256, 065, 047, 123, 890, 121, 009}

**1 ^{st} Iteration:**

256 |
055 |
047 |
123 |
807 |
121 |
009 |

The numbers at the rightmost position are **6, 5, 7, 3, 7, 1, 9**

We will arrange them from lowest to highest using count sort.

123 |
121 |
055 |
256 |
047 |
807 |
009 |

As we can see that there are two numbers whose rightmost digit is 7 which are **047** and **807** but as we have discussed earlier that we need to maintain relative order to sort the numbers, this is the reason we have put **047** before **807**, thereby maintaining the relative order of the numbers.

**2 ^{nd} Iteration:**

123 | 121 | 055 | 256 | 047 | 807 | 009 |

For the second iteration, we will look at the tens place of all the numbers.

123 |
121 |
055 |
256 |
047 |
807 |
009 |

The numbers at the 2^{nd} rightmost position are **2, 2, 5, 5, 4, 0, 0**

We will arrange them from lowest to highest using count sort while maintaining the relative order where digits match.

807 |
009 |
121 |
123 |
047 |
055 |
256 |

As we can see that in numbers **807** and **009**, the tens place is 0, we just maintain the previous order where **807** came before **009** which is why we have put **807** before 009 in the array.

The same reasoning applies to **121** and **123** as well as **055** and **256**.

**3 ^{rd} Iteration:**

807 | 009 | 121 | 123 | 047 | 055 | 256 |

Here we will look at the hundred’s place of all the numbers in the array and sort according to that digit.

807 |
009 |
121 |
123 |
047 |
055 |
256 |

The numbers at the hundred’s place or 3^{rd} rightmost position are **8, 0, 1, 1, 0, 0, 2**

009 |
047 |
055 |
121 |
123 |
256 |
807 |

We have reached the end of the iteration and we have sorted our array as well.

After sorting, we have the following array:

009 | 047 | 055 | 121 | 123 | 256 | 807 |

Here is source code of the C Program to Implement Radix Sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program to Implement Radix Sort`

`*/`

`#include<stdio.h>`

`#include<stdlib.h>`

int *Radix_sort(int *arr, int size);

int *Count_sort(int *arr, int size, int Exponent);

int maximum(int *arr,int length);

int minimum(int *arr,int length);

int main()

`{`

int i, size;

int *arr;

printf("Enter the array size: ");

scanf("%d",&size);

arr = (int *) malloc( sizeof( int ) * size );

if(arr==NULL)

`{`

exit(-1);//abnormal termination.

`}`

`else`

`{`

`// Entering the array values`

printf("Enter the array\n");

for(i = 0; i < size; i++)

`{`

printf("arr[ %d ] = ",i);

scanf("%d",&arr[i]);

`}`

printf("Array before sorting:\n");

for(i = 0; i < size; i++)

`{`

printf("arr[%d] = %d\n",i,arr[i]);

`}`

arr = Radix_sort(arr,size);

`}`

printf("ARRAY AFTER SORTING: \n");

for(int i=0;i<size;i++)

`{`

printf("arr[ %d ] = %d \n",i ,arr[i]);

`}`

`}`

int *Radix_sort(int *arr, int size)

`{`

int Max_of_arr = maximum(arr, size);

int Exponent = 1;

int count = 0;

while(Exponent <= Max_of_arr)

`{`

arr = Count_sort(arr, size, Exponent);

Exponent= Exponent* 10;

`//uncomment the loop to see how sorting happens digit after moving from LSB to MSB.`

`/*`

`printf("ARRAY AFTER SORTING: %d digits from rightmost element\n",count);`

`for(int i=0;i<size;i++)`

`printf("arr[ %d ] = %d \n",i ,arr[i]);`

`count++;`

`*/`

`}`

return arr;

`}`

int *Count_sort(int *arr, int size, int Exponent)

`{`

int range = 10;

int *frequency_array ;

frequency_array = (int*)malloc(sizeof(int)* range);

if(frequency_array == NULL)

`{`

exit(-1);

`}`

int sum=0;

for(int i=0; i<range; i++)

`{`

frequency_array[ i ]=0;

`}`

for(int i=0;i<size;i++)

`{`

frequency_array[ (arr[i]/Exponent)%10 ]++;

`}`

for(int i =0; i<range;i++)

`{`

sum = sum + frequency_array[i];

frequency_array[i] = sum;

`}`

int *new_arr;//new array to store the result.

new_arr = (int *)malloc(sizeof(int) *size);

if(new_arr == NULL)

`{`

exit(-1);

`}`

`else`

`{`

int pos;

for(int i=size-1; i>=0 ;i-- )

`{`

pos = frequency_array[(arr[i]/Exponent)%10]-1;

new_arr[ pos ] = arr[ i ];

frequency_array [(arr[i]/Exponent)%10]--;

`}`

`}`

return new_arr;

`}`

int maximum(int *arr, int length)

`{`

int max=INT_MIN;

for( int i=0 ; i<length ; i++ )

`{`

if(arr[i]>max)

max=arr[i];

`}`

return max;

`}`

int minimum(int *arr, int length)

`{`

int min=INT_MAX;

for( int i=0 ; i<length ; i++ )

`{`

if(arr[i]<min)

min=arr[i];

`}`

return min;

`}`

1. Take an input from the user and store it in **arr** variable.

2. In the above example, we can see that we have repeated the process 3 times here because the largest element of the array, which is 807, has 3 digits. Therefore, we will need to repeat the loop (number of digits in the largest array element) many times. For this, we will find the largest element.

3. Then create a variable **Exponent**, **Exponent** here defines which place value of the elements in the array is taken into consideration while sorting the array.

4. Initialize the **Exponent** to 1. That is, start the process from the 1’s place.

5. Then we continuously multiply it by 10, for example, 1 for one’s place, 10 to ten’s place, 100 for the hundred’s place, etc.

6. We pass the array to count sort with Exponent value and size of the array to sort the array through a stable sort method.

**Time complexity: O (d(n + b))**

Radix Sort takes O (d(n + b)) time, where b is the base for representing numbers; we used a decimal number system with a base of 10.

n = the number of elements in the array.

d = the maximum number of digits in the array.

**Space complexity: O (n + n + k)**

The space complexity of the radix sort algorithm is O (n + n + k), because we utilised another array of the same size as the input array to store the items in sorted order.

**Testcase 1:** In this case, we enter “7” as array size and the elements “256, 55, 47, 123, 807, 121 and 9” as input.

Enter the array size: 7 Enter the array arr[0] = 256 arr[1] = 55 arr[2] = 47 arr[3] = 123 arr[4] = 807 arr[5] = 121 arr[6] = 9 Array Before Sorting: arr[0] = 256 arr[1] = 55 arr[2] = 47 arr[3] = 123 arr[4] = 807 arr[5] = 121 arr[6] = 9 Array After Sorting: arr[0] = 9 arr[1] = 47 arr[2] = 55 arr[3] = 121 arr[4] = 123 arr[5] = 256 arr[6] = 807

**Testcase 2:** In this case, we enter “5” as array size and the elements “56, 1223, 122, 6543 and 23” as input.

Enter the array size: 5 Enter the array arr[0] = 56 arr[1] = 1223 arr[2] = 122 arr[3] = 6543 arr[4] = 23 Array Before Sorting: arr[0] = 56 arr[1] = 1223 arr[2] = 122 arr[3] = 6543 arr[4] = 23 Array After Sorting: arr[0] = 23 arr[1] = 56 arr[2] = 122 arr[3] = 1223 arr[4] = 6543

**Note:** Non-comparative radix sort can only sort positive integers in a collection of elements. That is, it cannot be applied to floating point integers and negative numbers.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**Next Steps:**

- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Practice BCA MCQs
- Buy C Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Apply for C Internship