What is Bucket Sort Algorithm in Data Structure? | Data Structure Tutorial

In this article, you will understand the Bucket Sort Algorithm of the Data Structure in better detail.

Bucket sort is the sorting algorithm that separates the unsorted array elements into multiple groups called buckets. Each bucket is then sorted with the help of suitable algorithms or by repetitively applying the same bucket algorithm. However, the sorted buckets are combined to make a final sorted array. 

Scatter Gather Approach

The bucket sort process can be understood using the scatter-gather approach. In this, elements are into the buckets then the elements in every bucket are sorted. Finally, the elements are clubbed together in order.

Working of Bucket Sort

1. Each slot of the array is used as a bucket for storing the elements of an array.
2. Insert the elements into the buckets from the array. The items are inserted into the array as per the range of the bucket. If we consider the integer numbers as input, we need to divide them by the interval to get the floor value.
3. The elements of each bucket are sorted using any of the stable sorting algorithms. Now, we have to use a quick sort.
4. The elements from every bucket are gathered. It is done by iterating through the bucket and adding an individual element into the original bucket in every cycle. The element from the bucket is erased once it is copied into the original array.

Bucket Sort Algorithm

bucket_sort()

    create N buckets every of which can hold a range of value

    for all the buckets

       Initialize each bucket with the 0 values

    for all the buckets

       keep the element into buckets matching the range

    for all the buckets

       sort elements in each bucket

    Keep the elements together from each bucket

end bucket_sort

Complexity

Time complexity

The best case complexity is O(n+k), the average case complexity is O(n), and the worst case complexity is O(n2).

The space complexity is O(n+k).

Applications of Bucket Sort Algorithm

• It is used when the input is uniformly distributed over a range.
• It is used when there are floating point values.