Radix Sort

Radix Sort:

Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest number among the list of numbers. For example, if the largest number is a 3 digit number then that list is sorted with 3 passes.

Example:

Original, unsorted list:

170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1s place) gives: 

[*Notice that we keep 802 before 2, because 802 occurred 

before 2 in the original list, and similarly for pairs 

170 & 90 and 45 & 75.]

170, 90, 802, 2, 24, 45, 75, 66

Sorting by next digit (10s place) gives: 

[*Notice that 802 again comes before 2 as 802 comes before 

2 in the previous list.]

802, 2, 24, 45, 66, 170, 75, 90

Sorting by the most significant digit (100s place) gives:

2, 24, 45, 66, 75, 90, 170, 802

Advantages

1. Fast when the keys are short i.e. when the range of the array elements is less.

2. Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.

Disadvantages:

1. Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts. Hence , for every different type of data it needs to be rewritten.

2. The constant for Radix sort is greater compared to other sorting algorithms.

3. It takes more space compared to Quicksort which is inplace sorting

Data structure:    Array

Worst-case time complexity: O(nk)

Average-case time complexity: Θ(nk)

Best-case time complexity: Ω(nk)

Worst-case space complexity: O(n+k)

CODE:

👇

1. #include<stdio.h>
2. int getMax(int a[ ], int n)
3. {
4.     int i, max=a[0];
5.     for(i=1; i<n; i++)
6.         if(a[i]>max)
7.             max=a[i];
8.     return max;        
9. }
10. 
    
11. void accpet(int a[ ], int n)
12. {
13.     for(int i=0; i<n; i++)
14.     scanf("%d",&a[i]);
15. }
16. 
    
17. void display(int a[ ],int n)
18. {
19.     for(int i=0; i<n; i++)
20.     printf("%d\t",a[i]);
21. }
22. 
    
23. void countingsort(int a[ ], int n, int pos)
24. {
25.     int res[20], i, cnt[10]={0};
26.     for(i=0; i<n; i++)
27.         cnt[(a[i]/pos)%10]++;
28.     for(i=1; i<10; i++)
29.         cnt[i] += cnt[i-1];
30.     for(i=n-1; i>=0; i--)
31.     {
32.         res[cnt[ (a[i]/pos)%10]-1]=a[i];
33.         cnt[(a[i]/pos)%10]--;
34.     }
35.     for(i=0; i<n; i++)
36.         a[i]=res[i];
37. }
38. 
    
39. void radixsort(int a[ ], int n)
40. {
41.     int m=getMax(a,n);
42.     for(int pos=1,pass=1; m/pos>0; pos*=10, pass++)
43.     {
44.         countingsort(a, n, pos);
45.         printf("\nAfter pass %d:",pass);
46.         display(a, n);
47.     }
48. }
49. 
    
50. int main()
51. {
52.     int a[20], n;
53.     printf("How many elements:");
54.     scanf("%d", &n);
55.     printf("Enter the %d elements:",n);
56.     accpet(a,n);
57.     radixsort(a,n);
58.     printf("\n\n>>Sorted Elements<<\n");
59.     display(a, n);
60.     return 0;
61. }
62. 
    

👉Execute👈

//Output

/*

How many elements:5

Enter the 5 elements:

123

951

789

456

357

After pass 1: 951 123 456 357 789

After pass 2: 123 951 456 357 789

After pass 3: 123 357 456 789 951

>>Sorted Elements<<

123 357 456 789 951

*/

                                                                 //ThE ProFessoR