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
Related Articles
Quick sort program in CBubble 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