Bucket Sort

What is Bucket sort?

Bucket sort, comparing sort algorithm dividing an array into a number of buckets, which are then categorized separately using an alternative sorting method, or by applying the bucket sort algorithm recursively

Working of Bucket sort

1. Find the largest number
2. Find the no. of digits in the largest number.
3. Consider the buckets from o to 9
4. Place the number in the appropriate buckets beginning with one’s own position.
5. Sort the numbers in each bucket from left to right.
6. Steps 4 and 5 should be repeated for each position of the given numbers.

Example of Bucket Sort

4 iteration bucket sort example

Pseudocode of Bucket Sort

1. bucketSort(a[], n)
2. Make a bunch of empty buckets preferably between 0 to 9.
3. Perform a[i] for each array elmt.Insert array elements into buckets
4. Use insertion sort to sort the items of particular buckets.
5. Lastly, aggregate or concatenate the buckets that have been sorted.
   bucket’s end Sort

Time_Bucket_Complexityy

Best Case scene- O((n+k))

Average Case scene- O((n * n))

Worst Case scene- O((n))

Space_Bucket_Complexity

O((n*k))

Advantages of Bucket Sort

1. Cos of the homogenous distribution of components, it is asymptotically fast.

2. The number of comparisons is reduced with bucket sort.

Disadvantages of Bucket Sort

1. Sorting all buckets demands considerable extra space.
2. It could be a steady sorting technique or not.

Application of Bucket Sort

Bucket sorts a huge number of floating-point values that are evenly scattered across the range of O to 1. There are floating-point values.

Programe of Bucket sort using C++

void buckt_sort_v(){

int big , nod =0,steps,noeb[10],i; // noeb=no of element in each buckets

bucket_v[10][10],loc, div = 1,a[100];

big= a[1]];

for. ( p=1;p<m;p++){

if(a[p]>big){

big=a[p];

}

while(big>0){

nod ++;

big=big/10;

}

}

for. ( steps=1;steps≤nod;steps++){

for. ( z=1; z<10 ; z++){

noeb[z]=0;

}

for. ( h=0;h<n;h++){

loc = (a[h]/div)/10;

bucket_v[loc][noeb][loc]++]=a[h];

}

}

for. ( l=0;l<n;l++){

for.( g=0;g<noeb[h];g++){

a[o++]=buckt_v[i][j];

}

div=div*10;

}