Radix Sort

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

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

-> Ten bins are maintained using linked lists

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

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

#include<iostream.h>
#include<math.h>

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

linkedlist* linkedlist::insert_at_end(int x,linkedlist*a)
{
 linkedlist *NEW;
 NEW=new linkedlist;

 NEW->n=x;
 NEW->next=NULL;

 if(a==NULL)
  a=NEW;
 else
 {
  linkedlist *l;
  l=a;
  while(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[10];
public:
 void input();
 void radixsort();
 void output();
};

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

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

 linkedlist obj;
 array=NULL;
 cout<<”Now enter your numbers ::\n”;
 for(int i=1;i<=n;i++)
 {
  int x;
  cin>>x;
  array=obj.insert_at_end(x,array);
 }
}

void sorting::radixsort()
{
 cout<<”\n\nsorting is done as follows\n\n”;
 int flag=1;
 int i=1;
 while(flag==1)
 {
  //Disperse the integers in to bins

  cout<<”Round < “<<i<<” > ::\n”;

  for(int j=0;j<=9;j++)
   bin[j]=NULL;
  linkedlist obj;

  int c=0;
  while(array!=NULL)
  {
   
   int x=array->n;
   int p=x/int (pow(10,i-1));

   bin[p%10]=obj.insert_at_end(x,bin[p%10]);
   if(p!=0)
    c++;

   array=array->next;
  }
  cout<<endl;

  //reset the flag
  if(c>0)
   flag=1;
  else
   flag=0;

  //display the bins
  for(j=0;j<=9;j++)
  {
   cout<<”Bin < “<<j<<” > ::”;
   obj.display(bin[j]);
  }

  //collect from the bins
  for(j=0;j<=9;j++)
  {
   while(bin[j]!=NULL)
   {
    array=obj.insert_at_end(bin[j]->n,array);
    bin[j]=bin[j]->next;
   }
  }
  cout<<”\nThe collected integers are ::\n”;
  obj.display(array);
  cout<<endl;
  i++;
 }
}

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

int main()
{
 sorting obj;
 obj.input();
 obj.radixsort();
 obj.output();
 return 0;
}

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

SAMPLE OUTPUT ::

*********************************************************
This program sorts the given integers in ascending order
   using radix sort algorithm
*********************************************************
Enter how many numbers you are going to enter ::7
Now enter your numbers ::
700
60
5
23
41
0
98
sorting is done as follows

Round < 1 > ::

Bin < 0 > ::700 60      0       NULL
Bin < 1 > ::41  NULL
Bin < 2 > ::NULL
Bin < 3 > ::23  NULL
Bin < 4 > ::NULL
Bin < 5 > ::5   NULL
Bin < 6 > ::NULL
Bin < 7 > ::NULL
Bin < 8 > ::98  NULL
Bin < 9 > ::NULL

The collected integers are ::
700     60      0       41      23      5       98      NULL

Round < 2 > ::

Bin < 0 > ::700 0       5       NULL
Bin < 1 > ::NULL
Bin < 2 > ::23  NULL
Bin < 3 > ::NULL
Bin < 4 > ::41  NULL
Bin < 5 > ::NULL
Bin < 6 > ::60  NULL
Bin < 7 > ::NULL
Bin < 8 > ::NULL
Bin < 9 > ::98  NULL

The collected integers are ::
700     0       5       23      41      60      98      NULL

Round < 3 > ::

Bin < 0 > ::0   5       23      41      60      98      NULL
Bin < 1 > ::NULL
Bin < 2 > ::NULL
Bin < 3 > ::NULL
Bin < 4 > ::NULL
Bin < 5 > ::NULL
Bin < 6 > ::NULL
Bin < 7 > ::700 NULL
Bin < 8 > ::NULL
Bin < 9 > ::NULL

The collected integers are ::
0       5       23      41      60      98      700     NULL

Round < 4 > ::

Bin < 0 > ::0   5       23      41      60      98      700     NULL
Bin < 1 > ::NULL
Bin < 2 > ::NULL
Bin < 3 > ::NULL
Bin < 4 > ::NULL
Bin < 5 > ::NULL
Bin < 6 > ::NULL
Bin < 7 > ::NULL
Bin < 8 > ::NULL
Bin < 9 > ::NULL

The collected integers are ::
0       5       23      41      60      98      700     NULL

After sorting the elements are ::
0       5       23      41      60      98      700     NULL
Press any key to continue

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