In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts work the other way around.
CODE:
/* WWW.CODE-AHOLIC.BLOGSPOT.IN-RADIX SORT */
#include <stdio.h>
#include <conio.h>
#define MAX 100
void print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
}
void radix_sort(int *a, int n)
{
int i, b[MAX], m = 0, exp = 1;
for (i = 0; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int box[10] = { 0 };
for (i = 0; i < n; i++)
box[a[i] / exp % 10]++;
for (i = 1; i < 10; i++)
box[i] += box[i - 1];
for (i = n - 1; i >= 0; i--)
b[--box[a[i] / exp % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
printf("\n\nPASS : ");
print(a, n);
}
}
void main()
{
int arr[MAX];
int i, num;
printf("\nEnter total elements (num < %d) : ", MAX);
scanf("%d", &num);
printf("\nEnter %d Elements : ", num);
for (i = 0; i < num; i++)
scanf("%d", &arr[i]);
printf("\nARRAY : ");
print(&arr[0], num);
radix_sort(&arr[0], num);
printf("\n\nSORTED : ");
print(&arr[0], num);
getch();
}