Write a C Program to implement address calculation sort.
Address calculation sort is the sorting method which sorts the given array by using insertion method.
In this algorithm, a hash function is used and applied to the each key. Result of hash function is placed in the linked lists. The hash function must be a order preserving function which places the elements in linked lists are called as sub files. An item is placed into a sub-file in correct sequence by using any sorting method. After all the elements are placed into subfiles, the list is concatenated to produce the sorted list.
 Address calculation sort is used to efficiently store non-contiguous keys (account numbers, part numbers, etc.) that may have wide gaps in their alphabetic and numeric sequences.
Read more about C Programming Language .

/***********************************************************
* You can use all the programs on  www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact info@c-program-example.com
* To find more C programs, do visit www.c-program-example.com
* and browse!
* 
*                      Happy Coding
***********************************************************/

#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");

  }


  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 %dn",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()*/

Read more Similar C Programs

Data Structures


 C Sorting

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!

To browse more C Programs visit this link