C++ Program for Bucket Sort
Description
Bucket sort is also called Radix Sort or Bin Sort.
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.
Advantage of bucket Sort
It is asymptotically fast because of uniform distribution.
It reduces the number of comparisons.
It is fast in comparison to bubble sort.
Disadvantages of bucket 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.
Time complexity Average Case = O(N)
worst case = O(N2)
Best case= O(N)
Space complexity = O(N)
C++ code for Bucket-Sort
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;
}
Output
Enter No. of elements
5
Enter Elements of array
234
876
123
987
456
Sorted array is
123
234
456
876
987
Comments