what is Radix Sort?

Radix Sort

Radix sort processes the elements the same way in which the names of the students are sorted according to their alphabetical order. There are 26 radix in that case due to the fact that, there are 26 alphabets in English. In the first pass, the names are grouped according to the ascending order of the first letter of names.

In the second pass, the names are grouped according to the ascending order of the second letter. The same process continues until we find the sorted list of names. The bucket are used to store the names produced in each pass. The number of passes depends upon the length of the name with the maximum letter.

In the case of integers, radix sort sorts the numbers according to their digits. The comparisons are made among the digits of the number from LSB to MSB. The number of passes depend upon the length of the number with the most number of digits.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n+k)	θ(nk)	O(nk)
Space Complexity			O(n+k)

Example

Consider the array of length 6 given below. Sort the array by using Radix sort.

A = {10, 2, 901, 803, 1024}

Pass 1: (Sort the list according to the digits at 0's place)

10, 901, 2, 803, 1024.

Pass 2: (Sort the list according to the digits at 10's place)

02, 10, 901, 803, 1024

Pass 3: (Sort the list according to the digits at 100's place)

02, 10, 1024, 803, 901.

Pass 4: (Sort the list according to the digits at 1000's place)

02, 10, 803, 901, 1024

Therefore, the list generated in the step 4 is the sorted list, arranged from radix sort.

Algorithm

• Step 1:Find the largest number in ARR as LARGE
• Step 2: [INITIALIZE] SET NOP = Number of digits
  in LARGE
• Step 3: SET PASS =0
• Step 4: Repeat Step 5 while PASS <= NOP-1
• Step 5: SET I = 0 and INITIALIZE buckets
• Step 6:Repeat Steps 7 to 9 while I
• Step 7: SET DIGIT = digit at PASSth place in A[I]
• Step 8: Add A[I] to the bucket numbered DIGIT
• Step 9: INCREMENT bucket count for bucket
  numbered DIGIT
  [END OF LOOP]
• Step 10: Collect the numbers in the bucket
  [END OF LOOP]
• Step 11: END

C Program

1. #include <stdio.h>  
2. int largest(int a[]);  
3. void radix_sort(int a[]);  
4. void main()  
5. {  
6.     int i;  
7.     int a[10]={90,23,101,45,65,23,67,89,34,23};       
8.     radix_sort(a);    
9.     printf("\n The sorted array is: \n");  
10.     for(i=0;i<10;i++)  
11.         printf(" %d\t", a[i]);  
12. }  
13.   
14. int largest(int a[])  
15. {     
16.     int larger=a[0], i;   
17.     for(i=1;i<10;i++)  
18.     {  
19.         if(a[i]>larger)  
20.         larger = a[i];  
21.     }  
22.     return larger;  
23. }  
24. void radix_sort(int a[])  
25. {  
26.     int bucket[10][10], bucket_count[10];  
27.     int i, j, k, remainder, NOP=0, divisor=1, larger, pass;  
28.     larger = largest(a);  
29.     while(larger>0)  
30.     {  
31.         NOP++;  
32.         larger/=10;  
33.     }  
34.     for(pass=0;pass<NOP;pass++) // Initialize the buckets  
35.     {  
36.         for(i=0;i<10;i++)  
37.         bucket_count[i]=0;  
38.         for(i=0;i<10;i++)  
39.         {  
40.             // sort the numbers according to the digit at passth place            
41.             remainder = (a[i]/divisor)%10;  
42.             bucket[remainder][bucket_count[remainder]] = a[i];  
43.             bucket_count[remainder] += 1;  
44.         }  
45.         // collect the numbers after PASS pass  
46.         i=0;  
47.         for(k=0;k<10;k++)  
48.         {  
49.             for(j=0;j<bucket_count[k];j++)  
50.             {  
51.                 a[i] = bucket[k][j];  
52.                 i++;  
53.             }  
54.         }  
55.         divisor *= 10;  
56.       
57. }  
58. }  

Output:

The sorted array is:
23
23
23
34
45
65
67
89
90
101

Java Program

1. public class Radix_Sort {  
2. public static void main(String[] args) {  
3.         int i;  
4.         Scanner sc = new Scanner(System.in);  
5.         int[] a = {90,23,101,45,65,23,67,89,34,23};  
6.         radix_sort(a);    
7.         System.out.println("\n The sorted array is: \n");  
8.         for(i=0;i<10;i++)  
9.             System.out.println(a[i]);  
10.     }  
11.   
12.     static int largest(inta[])  
13.     {     
14.         int larger=a[0], i;   
15.         for(i=1;i<10;i++)  
16.         {  
17.             if(a[i]>larger)  
18.             larger = a[i];  
19.         }  
20.         returnlarger;  
21.     }  
22.     static void radix_sort(inta[])  
23.     {  
24.         int bucket[][]=newint[10][10];  
25.         int bucket_count[]=newint[10];  
26.         int i, j, k, remainder, NOP=0, divisor=1, larger, pass;  
27.         larger = largest(a);  
28.         while(larger>0)  
29.         {  
30.             NOP++;  
31.             larger/=10;  
32.         }  
33.         for(pass=0;pass<NOP;pass++) // Initialize the buckets  
34.         {  
35.             for(i=0;i<10;i++)  
36.             bucket_count[i]=0;  
37.             for(i=0;i<10;i++)  
38.             {  
39.                 // sort the numbers according to the digit at passth place            
40.                 remainder = (a[i]/divisor)%10;  
41.                 bucket[remainder][bucket_count[remainder]] = a[i];  
42.                 bucket_count[remainder] += 1;  
43.             }  
44.             // collect the numbers after PASS pass  
45.             i=0;  
46.             for(k=0;k<10;k++)  
47.             {  
48.                 for(j=0;j<bucket_count[k];j++)  
49.                 {  
50.                     a[i] = bucket[k][j];  
51.                     i++;  
52.                 }  
53.             }  
54.             divisor *= 10;  
55.         }  
56.     }  
57. }  

Output:

The sorted array is:
23
23
23
34
45
65
67
89
90
101

C# Program

1. using System;  
2. public class Radix_Sort {  
3. public static void Main()   
4. {  
5.         int i;  
6.         int[] a = {90,23,101,45,65,23,67,89,34,23};  
7.         radix_sort(a);    
8.         Console.WriteLine("\n The sorted array is: \n");  
9.         for(i=0;i<10;i++)  
10.             Console.WriteLine(a[i]);  
11.     }  
12.   
13.     static int largest(int[] a)  
14.     {     
15.         int larger=a[0], i;   
16.         for(i=1;i<10;i++)  
17.         {  
18.             if(a[i]>larger)  
19.             larger = a[i];  
20.         }  
21.         return larger;  
22.     }  
23.     static void radix_sort(int[] a)  
24.     {  
25.         int[,] bucket=new int[10,10];  
26.         int[] bucket_count=new int[10];  
27.         int i, j, k, remainder, NOP=0, divisor=1, larger, pass;  
28.         larger = largest(a);  
29.         while(larger>0)  
30.         {  
31.             NOP++;  
32.             larger/=10;  
33.         }  
34.         for(pass=0;pass<NOP;pass++) // Initialize the buckets  
35.         {  
36.             for(i=0;i<10;i++)  
37.             bucket_count[i]=0;  
38.             for(i=0;i<10;i++)  
39.             {  
40.                 // sort the numbers according to the digit at passth place            
41.                 remainder = (a[i]/divisor)%10;  
42.                 bucket[remainder,bucket_count[remainder]] = a[i];  
43.                 bucket_count[remainder] += 1;  
44.             }  
45.             // collect the numbers after PASS pass  
46.             i=0;  
47.             for(k=0;k<10;k++)  
48.             {  
49.                 for(j=0;j<bucket_count[k];j++)  
50.                 {  
51.                     a[i] = bucket[k,j];  
52.                     i++;  
53.                 }  
54.             }  
55.             divisor *= 10;  
56.         }  
57.     }  
58. }  

Output:

The sorted array is:
23
23
23
34
45
65
67
89
90
101