#include <stdio.h>
#include <conio.h>
#define size 10
int largest(int arr[], int n);
void radix_sort(int arr[], int n);
void main() {
int arr[size], i, n;
//enter the numbers of elements in array
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
//enter array elements
printf("\n Enter the elements of the array: ");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//call the radix sort function
radix_sort(arr, n);
printf("\n The sorted array is: \n");
for (i = 0; i < n; i++)
{
printf(" %d\t", arr[i]);
}
}
//funtion to find largest element
int largest(int arr[], int n) {
int large = arr[0], i;
for (i = 1; i < n; i++) {
if (arr[i] > large)
large = arr[i];
}
return large;
}
//radix sort function, takes array data and count of elements
void radix_sort(int arr[], int n) {
int bucket[size][size], bucket_count[size];
int i, j, k, remainder, NOP = 0, divisor = 1, large, pass;
large = largest(arr, n);
while (large > 0) {
NOP++;
large /= size;
}
for (pass = 0; pass < NOP; pass++) // Initialize the buckets
{
for (i = 0; i < size; i++)
bucket_count[i] = 0;
for (i = 0; i < n; i++) {
// sort the numbers according to the digit at passth place
remainder = (arr[i] / divisor) % size;
bucket[remainder][bucket_count[remainder]] = arr[i];
bucket_count[remainder] += 1;
}
// collect the numbers after Nth PASS pass
i = 0;
for (k = 0; k < size; k++) {
for (j = 0; j < bucket_count[k]; j++) {
arr[i] = bucket[k][j];
i++;
}
}
divisor *= size;
}
}
