Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
#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);
    

}