Address Calculation Sort

/***************************************************************

-> This program is to sort the given integers
   in ascending order using address calculation sort

-> bins are maintained using linked lists

-> With the hash function used in the program it is
   only possible to sort integers that are < 100

-> This program works in microsoft vc++ 6.0 environment.

*****************************************************************/

#include<iostream.h>

class linkedlist
{
private:
 int n;
 linkedlist *next;
public:
 linkedlist* insert(int,linkedlist*);
 void display(linkedlist*);
 friend class sorting;
};

linkedlist* linkedlist::insert(int x,linkedlist*a)
{
 linkedlist *NEW;
 NEW=new linkedlist;
 NEW->n=x;
 NEW->next=NULL;

 if(a==NULL)
  a=NEW;
 else          // search for the correct position to insert
 {
  linkedlist *l;
  l=a;
  if(x<l->n)
  {
   NEW->next=l;
   a=NEW;
  }
  else
  {
   while( l->n<x && l->next!=NULL )
    l=l->next;
   l->next=NEW;
  }
 }
 return a;
}

void linkedlist::display(linkedlist*a)
{
 while(a!=NULL)
 {
  cout<<a->n<<‘\t';
  a=a->next;
 }
 cout<<“NULL\n”;
}

class sorting
{
private:
 int n;
 linkedlist *array;
 linkedlist *bin[6];
public:
 void input();
 void add_calc_sort();
 void output();
};

void sorting::input()
{
 cout<<“*********************************************************\n”;
 cout<<“This program sorts the given integers in ascending order\n”
  <<”   using address calculation sort algorithm \n”;
 cout<<“*********************************************************\n”;

 cout<<“Enter how many numbers you are going to enter ::”;
 cin>>n;

 array=NULL;
 cout<<“Now enter your numbers only in the range (0-99) ::\n”;
 for(int i=1;i<=n;i++)
 {
  int x;
  cin>>x;

  linkedlist *l;

  linkedlist *NEW;
  NEW=new linkedlist;
  NEW->n=x;
  NEW->next=NULL;

  if(array==NULL)
   array=NEW;
  else
   l->next=NEW;
  l=NEW;
 }
}

void sorting::add_calc_sort()
{
 //Hash the numbers in to the five bins

 linkedlist obj;
 int i;
 for(i=1;i<=5;i++)
  bin[i]=NULL;

 while(array!=NULL)
 {
  if( array->n >=0 && array->n <=19)
   bin[1]=obj.insert(array->n,bin[1] );
  else if( array->n >=20 && array->n <=39)
   bin[2]=obj.insert(array->n,bin[2] );
  else if( array->n >=40 && array->n <=59)
   bin[3]=obj.insert(array->n,bin[3] );
  else if( array->n >=60 && array->n <=79)
   bin[4]=obj.insert(array->n,bin[4] );
  else if( array->n >=80 && array->n <=99)
   bin[5]=obj.insert(array->n,bin[5] );

  array=array->next;
 }

 cout<<“\nThe contents of the bins are ::\n”;
 for(i=1;i<=5;i++)
 {
  cout<<” ( “<<i<<” ) ::”;
  obj.display(bin[i]);
 }

 //collect from all the bins

 array=NULL;
 for(i=1;i<=5;i++)
 {
  linkedlist *l;
  while(bin[i]!=NULL)
  {
   linkedlist *NEW;
   NEW=new linkedlist;

   NEW->n=bin[i]->n;
   NEW->next=NULL;

   if(array==NULL)
    array=NEW;
   else
    l->next=NEW;
   l=NEW;

   bin[i]=bin[i]->next;
  }
 }
}

void sorting::output()
{
 cout<<“After sorting the elements are ::\n”;
 linkedlist obj;
 obj.display(array);
}

int main()
{
 sorting obj;
 obj.input();
 obj.add_calc_sort();
 obj.output();
 return 0;
}
/*****************************************************************

SAMPLE OUTPUT ::

*********************************************************
This program sorts the given integers in ascending order
   using address calculation sort algorithm
*********************************************************
Enter how many numbers you are going to enter ::7
Now enter your numbers only in the range (0-99) ::
70
65
60
55
50
45
40

The contents of the bins are ::
 ( 1 ) ::NULL
 ( 2 ) ::NULL
 ( 3 ) ::40     45      50      55      NULL
 ( 4 ) ::60     65      70      NULL
 ( 5 ) ::NULL
After sorting the elements are ::
40      45      50      55      60      65      70      NULL
Press any key to continue

************************************************************************/

About these ads