Bucket Sort: In the sorting algorithm, we create buckets and put elements into them. We can apply some sorting algorithm (insertion sort) to sort the elements in each bucket. Finally, we take the elements out and join them to get the sorted result.

The bucket sort assumes that the input is generated by a random process that distributes the elements uniformly over the interval (0,1).

The idea of ​​bucket sort is to divide the interval 0 to 1 into “n” equal-sized sub-intervals or buckets, and then distribute the n input number to the bucket.

The bucket sort program requires an auxiliary array X [0, 1, 2, …., n-1] of the linked list.

Complexity table of bucket sort

ComplexityBest caseAverage caseWorst case
TimeO(n + k)O(n + k)O(n2)
Space  O(n)

Algorithm of bucket sort

For example: Suppose we have the following array, which we have to sort.

11861252

Step 1: Create a new array, and this array size is 10. Every field of this array is used as a bucket.  

Step 2: Insert the array element into the new array bucket, and these elements will be added according to the range of the bucket.    

Step 3: Gather the element form each bucket.  

Bucket sort program in C language:

Bucket sort program in java language:

Pin It on Pinterest

Share This