Radix Sort

Radix sort is a linear sorting algorithm that is also called bucket sort. It uses the concept of sorting names in alphabetical orders.

The Quick Sort, Merge Sort, Heap Sort and Selection Sort are comparison based algorithms. But the radix sort is not comparison based algorithm. It is linear sorting and best than comparison sorting.

Complexity of Radix Sort

Suppose n is the number of element in an array.

Best Case Time Complexity - O(n)

Radix Sort Example

Suppose the input array is -

12, 72, 28, 69, 34, 101, 134

As per radix sort algorithm, first sort the array according to the one's digit.

12, 72, 28, 69, 34, 101, 134
0: 
1: 101
2: 12, 72
3: 
4: 34, 134
5:
6:
7:
8: 28
9: 69

So, the array becomes - 
101, 12, 72, 34, 134, 28, 69

Again sort the array according to the ten's digit.

101, 12, 72, 34, 134, 28, 69
0: 101
1: 12
2: 28
3: 34, 134
4: 
5:
6: 69
7: 72
8: 
9: 

So, the array becomes - 
101, 12, 28, 34, 134, 69, 72

Again sort the array according to the hundred's digit.

101, 12, 28, 34, 134, 69, 72
0: 
1: 101, 134
2: 
4: 
5:
6: 
7: 
8: 
9: 

So, the array becomes - 
12, 28, 34, 69, 72, 101, 134

Radix Sort Program in C

#include<stdio.h>

int main()
{
	int i, n, a[10];
	printf("Enter the number of elements: ");
	scanf("%d",&n);
	printf("Enter %d numbers : \n",n);
	for(i = 0; i < n; i++)
	{
		scanf("%d",&a[i]);
	}
	radix_sort(a,n);
	printf("\n Sorted numbers using Radix Sort : \n");
	for(i = 0; i < n; i++)
		printf("  %d",a[i]);
		printf("\n");
		return 0;
}

int getMax(int a[], int n)
{
	int max_value = a[0], i;
	for(i = 1; i < n; i++)
	{
		if(max_value < a[i])
		max_value = a[i];
	}
	return max_value;
}
// radix sort
void radix_sort(int a[], int n)
{
	int bucket[10][10], bucket_count[10];
	int i, j, k, remainder, NOP=0, divisor=1, large, pass;
	large = getMax(a, n);
	printf("\n Largest element : %d\n",large);
	while(large > 0)
	{
		NOP++;
		large/=10;
	}
	for(pass = 0; pass < NOP; pass++)
	{
		for(i = 0; i < 10; i++)
		{
			  bucket_count[i] = 0;
		}
		for(i = 0; i < n; i++)
		{
			  remainder = (a[i] / divisor) % 10;
			  bucket[remainder][bucket_count[remainder]] = a[i];
			  bucket_count[remainder] += 1;
		}
		
		i = 0;
		for(k = 0; k < 10; k++)
		{
			  for(j = 0; j < bucket_count[k]; j++)
			  {
					a[i] = bucket[k][j];
					i++;
			  }
		}
		divisor *= 10;
		printf("\n PASS %d :\n",pass+1);
		for(i = 0; i < n; i++)
			printf("  %d",a[i]);
			printf("\n");
	}
}

Output of the above program :

Enter the number of elements: 10
Enter 10 numbers : 
09
23
15
52
142
163
12
15
62
72

Largest element : 163

PASS 1 :
52  142  12  62  72  23  163  15  15  9

PASS 2 :
9  12  15  15  23  142  52  62  163  72

PASS 3 :
9  12  15  15  23  52  62  72  142  163

Sorted numbers using Radix Sort : 
9  12  15  15  23  52  62  72  142  163