/*Program of sorting using address calculation sort*/
#include<stdio.h>
#include<malloc.h>
#define MAX 20

struct  node
{
    int info ;
    struct node *link;
};
struct node *head[10];
int n,i,arr[MAX];
main()
{

    int i;
    printf("Enter the number of elements in the list : ");
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        printf("Enter element %d : ",i+1);
        scanf("%d",&arr[i]);
    }/*End of for */

    printf("Unsorted list is :\n");
    for(i=0;i<n;i++)
        printf("%d  ",arr[i]);
    printf("\n");
    addr_sort();
    printf("Sorted list is :\n");
    for(i=0;i<n;i++)
        printf("%d  ",arr[i]);
    printf("\n");
}/*End of main()*/

addr_sort()
{
    int i,k,dig;
    struct node *p;
    int addr;
    k=large_dig();
    for(i=0;i<=9;i++)
        head[i]=NULL;
    for(i=0;i<n;i++)
    {
        addr=hash_fn( arr[i],k );
        insert(arr[i],addr);
    }

    for(i=0; i<=9 ; i++)
    {
        printf("head(%d) -> ",i);
        p=head[i];
        while(p!=NULL)
        {
            printf("%d ",p->info);
            p=p->link;
        }
        printf("\n");
    }

    /*Taking the elements of linked lists in array*/
    i=0;
    for(k=0;k<=9;k++)
    {
        p=head[k];
        while(p!=NULL)
        {
            arr[i++]=p->info;
            p=p->link;
        }
    }
}/*End of addr_sort()*/

/*Inserts the number in sorted linked list*/
insert(int num,int addr)
{
    struct node *q,*tmp;
    tmp= malloc(sizeof(struct node));
    tmp->info=num;
    /*list empty or item to be added in begining */
    if(head[addr] == NULL || num < head[addr]->info)
    {
        tmp->link=head[addr];
        head[addr]=tmp;
        return;
    }
    else
    {
        q=head[addr];
        while(q->link != NULL && q->link->info < num)
            q=q->link;
        tmp->link=q->link;
        q->link=tmp;
    }
}/*End of insert()*/

/* Finds number of digits in the largest element of the list */
int large_dig()
{

    int large = 0,ndig = 0 ;

    for(i=0;i<n;i++)
    {
        if(arr[i] > large)
            large = arr[i];
    }
    printf("Largest Element is %d , ",large);
    while(large != 0)
    {
        ndig++;
        large = large/10 ;
    }

    printf("Number of digits in it are %d\n",ndig);
    return(ndig);
} /*End of large_dig()*/

hash_fn(int number,int k)
{
    /*Find kth digit of the number*/
    int digit,addr,i;
    for(i = 1 ; i <=k ; i++)
    {
        digit = number % 10 ;
        number = number /10 ;
    }
    addr=digit;
    return(addr);
}/*End of hash_fn()*/

/*
hash_fn(int number,int k)
{

    int addr,i,large=0;
    float tmp;

    for(i=0;i<n;i++)
    {
        if(arr[i] > large)
            large = arr[i];
    }
    tmp=(float)number/large;
    addr=tmp*9;
    return(addr);
}/*End of hash_fn()*/