Radix sort program in C

In this post, you will learn how to write a radix sort program in the C programming language.

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

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 a linear sorting and better than comparison sorting.

Complexity of Radix Sort

Suppose n is the number of elements 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 the 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 code:

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

Quick sort program in C
Bubble sort program in C++
Bubble sort program in C
Selection sort program in Python
Python program for insertion sort
Quick sort program in Python
C program for selection sort
C program to find greatest of three numbers
C program for addition of two numbers
C program to calculate compound interest
C program to find the ASCII value of a character
C program to convert Decimal to Octal
C program to convert decimal to binary
Write a C program to calculate Simple Interest
C program to check whether a number is even or odd
C program to reverse a number
C program to check palindrome number
C program to check whether an alphabet is a vowel or consonant
Program to find square root of a number in C
C program to check whether a number is positive or negative