Bucket Sort

Facebooktwitterredditpinterestlinkedinmailby feather

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

Complexity Best case Average case Worst case
Time O(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.

11 8 6 1 25 2

Bucket sort program in C language:

Bucket sort program in java language:

Facebooktwitterredditpinterestlinkedinmailby feather