Sorting – Address Calculation Sort (Hashing)

Sorting – Address Calculation Sort (Hashing)

• In this method a function f is applied to each key.
• The result of this function determines into which of the several subfiles the record is to be placed.
• The function should have the property that: if x <= y ,  f (x) <= f (y), Such a function is called order preserving.
• An item is placed into a subfile in correct sequence by placing sorting method – simple insertion is often used.

Example:

25         57         48         37         12         92         86         33

Let us create 10 subfiles.  Initially each of these subfiles is empty.  An array of pointer f(10) is declared, where f(i) refers to the first element in the file, whose first digit is i.  The number is passed to hash function, which returns its last digit (ten’s place digit), which is placed at that position only, in the array of pointers.

num=    25         –           f(25) gives 2
57         –           f(57) gives 5
48         –           f(48) gives 4
37         –           f(37) gives 3
12         –           f(12) gives 1
92         –           f(92) gives 9
86         –           f(86) gives 8
33         –           f(33) gives 3 which is repeated.

Thus it is inserted in 3^rd subfile (4^th)  only, but must be checked with the existing elements for its proper position in this subfile.

Arrangement of nodes in subfiles

Efficiency:  If all the elements (n) are uniformly distributed over m subfiles then n/m is approximately 1, time of the sort is near O(n).

On the other hand if maximum elements accommodate in one or two subfiles, then n/m is much larger significant work is required to insert its proper subfile at its proper position and efficiency is O(n²).

Program to implement Address Calculation Sort:

/*Address Calculation Sort*/
/*It uses a hash function that can sort only 2 digit nos.*/

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

#define MAX 5

struct list
{int info;
struct list *next;
}*node[10]={NULL};

struct list *create()
{
struct list *temp=(struct list *)malloc(sizeof(struct list));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct list *makenode(int num)
{
struct list *temp;
temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}

struct list *insert(struct list *s,int num)
{
struct list *ptr,*temp;
ptr=s;
temp=makenode(num);
if(s==NULL)
s=temp;
else
{
/*code for placing new node at appropriate
position in the subfile*/
while((ptr->next->info<=num) && (ptr->next!=NULL))
{ptr=ptr->next;
}
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

/*A hash function that operates upon two digit
numbers only*/

int hashfun(int n)
{return (n/10);
}

void addr_calc(int arr[],int size)
{
int i,j=0,pos;
for(i=0;i<size;i++)
{pos=hashfun(arr[i]);
node[pos]=insert(node[pos],arr[i]);
}
for(i=0;i<10;i++)
{while(node[i]!=NULL)
{arr[j++]=node[i]->info;
node[i]=node[i]->next;
}
}
printf(“\nSorted output is: “);
for(i=0;i<size;i++)
printf(“%d\t”,arr[i]);
getch();
}

void main()
{
int arr[MAX],i,n;
clrscr();
printf(“Enter total numbers to sort?”);
scanf(“%d”,&n);
printf(“Enter numbers?”);
for(i=0;i<n;i++)
scanf(“%d”,&arr[i]);
addr_calc(arr,n);
}