Address Calculation Sort

C Program to sort array elements using Address Calculation Sort

#include<stdio.h>
#include<stdlib.h>

struct node
{
       int info;
       struct node *link;
};
typedef struct node * NODE;
NODE head[10];
int n,i,a[20];

int hash_fn(int number,  int k)
{
             /*Find kth digit of the number :example: if its 356 then kth digit will be 3 or if its 29 then kth digit will be 2*/
        int digit, i;
        for(i = 1 ; i <=k ; i++)
        {
              digit = number % 10 ;
              number = number /10 ;
        }
        return digit;       //address
}


/* Finds number of digits in the largest element of the list */
int large_dig()
{
       int large = a[0],ndig = 0 ;
       for(i=0;i<n;i++)                        /*First find the largest number in the array*/
      {
              if(a[i] > large)
                      large = a[i];
       }
       printf("\nLargest Element is %d",large);

      while(large != 0)           /*Finds number of digits in the largest number*/
      {
               ndig++;
               large = large/10 ;
      }
      printf("\nNumber of digits in it are %d", ndig);
      return(ndig);
}


/*Inserts the number in linked list in sorted manner*/
void insert(int num, int addr)
{
      NODE cur ,tmp;
      tmp = (NODE)malloc(sizeof(struct node));
      tmp->info = num;

      /*list empty or item to be added in beginning */
       if(head[addr] == NULL || num < head[addr]->info)
      {
            tmp->link = head[addr];
            head[addr] = tmp;
            return;
      }
     else
     {
            cur = head[addr];
            while(cur->link != NULL && cur->link->info < num)
                      cur = cur->link;
            tmp->link = cur->link;
            cur->link = tmp;
     }
}

void addr_sort()
{
       int i, k, dig, addr;
       NODE p;
       k = large_dig();        /*number of digits in the largest number*/
       for(i=0;i<=9;i++)
               head[i]=NULL;
       for(i=0;i<n;i++)
      {
               addr = hash_fn(a[i], k);
               insert(a[i], addr);
       }

      for(i=0; i<=9 ; i++)
      {
              printf("\nhead(%d) -> ", i);
              p = head[i];
              while(p!=NULL)
             {
                    printf("%d ", p->info);
                    p = p->link;
              }
      }
     /*Taking the elements of linked lists in array*/
      i = 0;
      for(k=0;k<=9;k++)
      {
               p = head[k];
               while(p!=NULL)
              {
                       a[i++] = p->info;
                       p = p->link;
               }
      }
}

void main()
{
      int i;
      printf("\nEnter the number of elements in the list : ");
      scanf("%d", &n);
      for(i=0;i<n;i++)
      {
             printf("\nEnter element %d : ",i+1);
             scanf("%d",&a[i]);
      }

      printf("\nUnsorted list is :\n");
      for(i=0;i<n;i++)
            printf("%d ",a[i]);

      addr_sort();
      printf("\nSorted list is :\n");
      for(i=0;i<n;i++)
              printf("%d ",a[i]);
}


Output:

Enter the number of elements in the list : 15
Enter element 1 : 12
Enter element 2 : 345
Enter element 3 : 567
Enter element 4 : 367
Enter element 5 : 789
Enter element 6 : 23
Enter element 7 : 15
Enter element 8 : 56
Enter element 9 : 567
Enter element 10 : 899
Enter element 11 : 123
Enter element 12 : 321
Enter element 13 : 678
Enter element 14 : 67
Enter element 15 : 45
Unsorted list is :
12   345   567  367   789   23   15   56   567   899   123   321   678   67   45
Largest Element is 899
Number of digits in it are 3

head(0) -> 12  15  23  45  56  67
head(1) -> 123
head(2) ->
head(3) -> 321  345  367
head(4) ->
head(5) -> 567  567
head(6) -> 678
head(7) -> 789
head(8) -> 899
head(9) ->
Sorted list is :
12   15   23   45   56   67   123   321   345   367   567   567   678   789  899