Bucket sort is a sorting technique in which elements are first uniformly divided into several groups called buckets.

Bucket sort is a method that can be used to sort a list of names alphabetically.

Here the base of radix is 26,( 26 letters of alphabet).

First of all the list of names is sorted according to the first letter of each name thus the names are arranged in 26 buckets.

In second pass, names are arranged according to second letter of each name and so o . This process depends on the length of the name with maximum letters.

suppose if no name contain more than 15 letters, the names are alphabetized with at most 15 passes.

to sort decimal numbers, where radix or base is 10, we need ten buckets. These buckets are numbered 0,1,2,3,4,5,6,7,8,9.

Unlike, sorting names, decimal numbers are sorted from right to left.

It is usually used to sort floating-point numbers.

It is asymptotically fast because of uniform distribution.

It reduces the number of comparisons.

It is fast in comparison to bubble sort.

It is not an in-place sorting because we need some extra space to sort the buckets.

It may or may not be the stable sorting algorithm.

It is not useful if we have large array because it increases the cost.

using namespace std;
void bucket_sort(int a[], int n)
{
int bucket[10][5];
int buck[10];
int b[10];
int i,j,k,l,num,divi,large,passes;
divi = 1;
num = 0;
large = a[0];
//finding largest element in the array
for(i=0 ; i<n ; i++)
{
if(a[i]>large)
{
large = a[i];
}
}
//finding number of passes required
while(large>0)
{
num++;
large = large/10 ;
}
for(passes=0 ; passes<num ; passes++)
{
for( k=0 ; k<10 ; k++)
{
buck[k]=0;
}
for( i=0 ; i<n ; i++)
{
l = ( a[i]/divi ) % 10;
bucket[l][buck[l]++] = a[i];
}
i=0;
for( k=0 ; k<10; k++)
{
for( j=0 ; j<buck[k] ; j++)
{
a[i++] = bucket[k][j];
}
}
divi=divi*10;
}
}
int main() {
int n , i ;
cout<<"Enter no. of element\n";
cin>>n;
int a[n];
cout<<"Enter element of array\n";
for( i=0; i<n ; i++)
{
cin>>a[i];
}
bucket_sort( a , n );
cout<<"Sorted array is\n";
for( i=0; i<n ; i++)
{
cout<<a[i]<<"\n";
}
return 0;
}

Enter No. of elements

5

Enter Elements of array

234

876

123

987

456

Sorted array is

123

234

456

876

987

## Comments