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
