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

-> 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>

{
private:
int n;
public:
friend class sorting;
};

{

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

if(a==NULL)
a=NEW;
else
{
l=a;
while(l->next!=NULL)
l=l->next;
l->next=NEW;
}
return a;
}

{
while(a!=NULL)
{
cout<<a->n<<‘\t’;
a=a->next;
}
cout<<“NULL\n”;
}

class sorting
{
private:
int n;
public:
void input();
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;

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);
}
}

{
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;

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”;
obj.display(array);
}

int main()
{
sorting obj;
obj.input();
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

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