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

class node
{
public:
float info;
node *next,*prev;
node(){next=prev=0;}
node(int n, node *ptr=0, node *ptr1=0)
{
info=n;
next=ptr;
prev=ptr1;
}
};

/* sort the link list of elements*/
void isort(node *head)
{
if (head == 0)
return;
float key;
node *j,*i, *q=0;

for(i=head->next;i!=0;i=i->next)
{
q=0;
key = i->info;
j=i->prev;
while(j!=0 && key < (j->info) )
{
j->next->info=j->info;
q = j;
j=j->prev;
}

if(q!=0)
q->info = key;
}

}


void bucket_sort(float *a,int n)
{
/* create buckets */
node* *b = new node* [n];
for(int i=0; i<n;i++)
b[i]=0;

/* step 2 begins - insert a[i] into buckets */
for(int i=0;i<n;i++)
{
int index=n*a[i];

node *temp=new node(sizeof(node));
temp->info=a[i];

if(b[index]==NULL)
{
b[index]=temp;
}
else
{
temp->next=b[index];
b[index]->prev=temp;
b[index]=temp;
}
} // end of for
/* step 2 ends */

/* step 3 begins - sort each bucket */
for(int i=0; i<n;i++)
{
isort(b[i]);
}
/* step 3 ends */

/* step 4 begins - concatenate all the buckets */
node *trav=0;
cout<<"\n\nSorted array is: \n";
for(int i=0; i<n;i++)
{
trav = b[i];
while(trav != 0)
{
cout<<trav->info<<" ";
trav = trav->next;
}
}
/* step 4 ends */
}

void main()
{
clrscr();

int n;
float *a;

cout<<"\n\t Enter the size of array : ";
cin>>n;

cout<<"\n\t Enter the elements of an array :\n";
a=new float[n];
for(int l=0;l<n;l++)
cin>>a[l];

cout<<"\n\t Unsorted array is..\n";
for(int l=0;l<n;l++)
cout<<a[l]<<" ";
cout<<"\n" ;

/* sort lements using buckt sort */
bucket_sort(a,n);

getch();
}