C Program to Implement Radix Sort

Problem Description

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.

Problem Solution

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}

1st Iteration:

advertisement
advertisement
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.

2nd Iteration:

Note: Join free Sanfoundry classes at Telegram or Youtube
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 2nd 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.

advertisement

3rd 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 3rd 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:

advertisement
009 047 055 121 123 256 807
Program/Source Code

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.

  1. /*
  2.  * C program to Implement Radix Sort
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7. int *Radix_sort(int *arr, int size);
  8. int *Count_sort(int *arr, int size, int Exponent);
  9. int maximum(int *arr,int length);
  10. int minimum(int *arr,int length);
  11. int main()
  12. {
  13.     int i, size;
  14.     int *arr;
  15.     printf("Enter the array size: ");
  16.     scanf("%d",&size);
  17.     arr = (int *) malloc( sizeof( int ) * size );
  18.     if(arr==NULL)
  19.     {
  20.         exit(-1);//abnormal termination.
  21.     }
  22.     else
  23.     {
  24.         // Entering the array values
  25.         printf("Enter the array\n");
  26.         for(i = 0; i < size; i++)
  27.         {
  28.             printf("arr[ %d ] = ",i);
  29.             scanf("%d",&arr[i]);
  30.         }
  31.         printf("Array before sorting:\n");
  32.         for(i = 0; i < size; i++)
  33.         {
  34.             printf("arr[%d] = %d\n",i,arr[i]);
  35.         }
  36.  
  37.         arr = Radix_sort(arr,size);
  38.     }
  39.     printf("ARRAY AFTER SORTING: \n");
  40.     for(int i=0;i<size;i++)
  41.     {
  42.         printf("arr[ %d ] = %d \n",i ,arr[i]);
  43.     }
  44. }
  45.  
  46. int *Radix_sort(int *arr, int size)
  47. {
  48.     int Max_of_arr = maximum(arr, size);
  49.     int Exponent = 1;
  50.     int count = 0;
  51.     while(Exponent <= Max_of_arr)
  52.     {
  53.         arr = Count_sort(arr, size, Exponent);
  54.         Exponent= Exponent* 10;
  55.         //uncomment the loop to see how sorting happens digit after moving from LSB to MSB.
  56.         /*
  57.             printf("ARRAY AFTER SORTING: %d digits from rightmost element\n",count);
  58.             for(int i=0;i<size;i++)
  59.                     printf("arr[ %d ] = %d \n",i ,arr[i]);
  60.             count++;
  61.         */
  62.     }
  63.     return arr;
  64. }
  65.  
  66. int *Count_sort(int *arr, int size, int Exponent)
  67. {
  68.     int range = 10;
  69.     int *frequency_array ;
  70.     frequency_array = (int*)malloc(sizeof(int)* range);
  71.     if(frequency_array == NULL)
  72.     {
  73.         exit(-1);
  74.     }
  75.     int sum=0;
  76.     for(int i=0; i<range; i++)
  77.     {
  78.         frequency_array[ i ]=0;
  79.     }
  80.  
  81.     for(int i=0;i<size;i++)
  82.     {
  83.         frequency_array[ (arr[i]/Exponent)%10 ]++;
  84.     }
  85.  
  86.     for(int i =0; i<range;i++)
  87.     {
  88.         sum = sum + frequency_array[i];
  89.         frequency_array[i] = sum;
  90.     }
  91.  
  92.     int *new_arr;//new array to store the result.
  93.     new_arr = (int *)malloc(sizeof(int) *size);
  94.     if(new_arr == NULL)
  95.     {
  96.         exit(-1);
  97.     }
  98.     else
  99.     {
  100.         int pos;
  101.         for(int i=size-1; i>=0 ;i-- )
  102.         {
  103.                 pos = frequency_array[(arr[i]/Exponent)%10]-1;
  104.                 new_arr[ pos ] = arr[ i ];
  105.                 frequency_array [(arr[i]/Exponent)%10]--;
  106.         }
  107.     }
  108.     return new_arr;
  109. }
  110. int maximum(int *arr, int length)
  111. {
  112.     int max=INT_MIN;
  113.     for( int i=0 ; i<length ; i++ )
  114.     {
  115.         if(arr[i]>max)
  116.             max=arr[i];
  117.     }
  118.     return max;
  119. }
  120. int minimum(int *arr, int length)
  121. {
  122.     int min=INT_MAX;
  123.     for( int i=0 ; i<length ; i++ )
  124.     {
  125.         if(arr[i]<min)
  126.             min=arr[i];
  127.     }
  128.     return min;
  129. }
Program Explanation

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.

Runtime Test Cases

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”.

If you find any mistake above, kindly email to [email protected]

Related Posts:

advertisement

Recommended Articles:

  1. C++ Program to Implement Radix Sort
  2. MSD Radix Sort Multiple Choice Questions and Answers (MCQs)
  3. Java Program to Implement Radix Sort
  4. C# Program to Implement Radix Sort
  5. Python Program to Implement Radix Sort
  6. LSD Radix Sort Multiple Choice Questions and Answers (MCQs)
  7. C++ Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
  8. C Program to Implement Selection Sort using Functions
  9. C Program to Sort N Numbers in Ascending Order using Bubble Sort
  10. C Program to Implement Bubble Sort
advertisement
Additional Resources:
Popular Pages:
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.