Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Bucket Sort

#include <iostream.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";

}
Bucket Sort program in C++

No comments:

Post a Comment

Search 24 Bytes