#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node{
int data;
struct node* link;
};
struct node* createnode(int data){
struct node* temp=(struct node*)malloc(sizeof(struct node));
temp->data=data;
temp->link=NULL;
return temp;
}
void printll(struct node* head){
while(head!=NULL){
printf("%d ",head->data);
head=head->link;
}
printf("\n");
}
struct node* radixsort(struct node* head,int size){
int i;
int divisor=10;
for(i=1;i<=size;i++,divisor*=10){
struct node* arr[10];
for(int k=0;k<10;k++){
arr[k]=NULL;
}
while(head!=NULL){
struct node* next=head->link;
int digit=(head->data%divisor)/(divisor/10);
// printf("%d %d %d %d\n",head->data,digit,divisor,head->data%divisor);
if(arr[digit]==NULL){
arr[digit]=head;
}
else{
struct node* curr=arr[digit];
while(curr->link!=NULL){
curr=curr->link;
}
curr->link=head;
}
head->link=NULL;
head=next;
}
int j;
for(j=0;j<10;j++){
// printf("%d: ",j);
// printll(arr[j]);
if(arr[j]==NULL){
continue;
}
else if(head==NULL){
head=arr[j];
}
else{
struct node* temp=head;
while(temp->link!=NULL){
temp=temp->link;
}
temp->link=arr[j];
}
}
// printf("ll\n");
// printll(head);
}
return head;
}
int main(){
int n;
printf("enter the size of array ");
scanf("%d",&n);
int x,max=-1;
struct node* head=NULL;
struct node* tail=NULL;
while(n--){
printf("enter the no ");
scanf("%d",&x);
if(x>max){
max=x;
}
struct node* curr= createnode(x);
if(head==NULL){
head=curr;
tail=curr;
}
else{
tail->link=curr;
tail=curr;
}
}
int size=0;
while(max!=0){
max=max/10;
size++;
}
printf("before Sorting\n");
printll(head);
head=radixsort(head,size);
printf("After sorting\n");
printll(head);
}