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



class element            //element 
{
public:
	int value;
	element *next;
	element()
	{
	value=NULL;
	next=NULL;
	}
};

class bucket           //bucket containing a perticular range of values    
{
public:
element *firstElement;
bucket()
{
firstElement = NULL;
}
};

void main()                     
{
	int lowend=0;         // minimum element 
	int highend=100;      //max element  
	int interval=10;      //number of intervals    
	const int noBuckets=(highend-lowend)/interval; //number of buckets required 
	bucket *buckets=new bucket[noBuckets];             
	bucket *temp;

	for(int a=0;a<noBuckets;a++)   //creation of required buckets    
	{
		temp=new bucket;
		buckets[a]=*temp;
	}

	cout<<"--------The Elements to be Sorted using Bucket sort are ------------------\n";
	int array[]={12,2,22,33,44,55,66,77,85,87,81,83,89,82,88,86,84,88,99};

	for(int j=0;j<19;j++)   //sending elments into appropriate buckets
	{
	cout<<array[j]<<endl;
	element *temp,*pre;
	temp=buckets[array[j]/interval].firstElement;
		if(temp==NULL)//if it is the first element of the bucket
		{
			temp=new element;
			buckets[array[j]/interval].firstElement=temp;
			temp->value=array[j];
		}
		else
		{
			pre=NULL;
				while(temp!=NULL)     //move till the appropriate position in the bucket
				   {
		       if(temp->value>array[j])
				   break;
				   pre=temp;
				   temp=temp->next;
				   }
				if(temp->value>array[j]) //if the new value is in betwen or at the begining
				{
					if(pre==NULL)  //insertion at first if the bucket has elements already
					{
						element *firstNode;
						firstNode=new element();
						firstNode->value=array[j];
						firstNode->next=temp;
						buckets[array[j]/interval].firstElement=firstNode;
					}
					else  //insertion at middle
					{
						element *firstNode;
						firstNode=new element();
						firstNode->value=array[j];
						firstNode->next=temp;
						pre->next=firstNode;
					}
				}
				else// if the new value is to be created at last of bucket
				{
					temp=new element;
					pre->next=temp;
					temp->value=array[j];
				}

		}
 }

	cout<<"------------------------The Sorted Elements Are---------------\n";
	for(int jk=0;jk<10;jk++)
	{
		element *temp;
		temp= buckets[jk].firstElement;
			while(temp!=NULL)
			{
				cout<<"*"<<temp->value<<endl;
				temp=temp->next;
			}
	}
	cout<<"--------------------------------END--------------------------------\n";

}