*62*

# Bucket Sort Algorithm

In this article, we will discuss the bucket sort Algorithm. The data items in the bucket sort are distributed in the form of buckets. In coding or technical interviews for software engineers, sorting algorithms are widely asked. So, it is important to discuss the topic.

Bucket sort is a sorting algorithm that separate the elements into multiple groups said to be buckets. Elements in bucket sort are first uniformly divided into groups called buckets, and then they are sorted by any other sorting algorithm. After that, elements are gathered in a sorted manner.

The basic procedure of performing the bucket sort is given as follows –

- First, partition the range into a fixed number of buckets.
- Then, toss every element into its appropriate bucket.
- After that, sort each bucket individually by applying a sorting algorithm.
- And at last, concatenate all the sorted buckets.

The advantages of bucket sort are –

- Bucket sort reduces the no. of comparisons.
- It is asymptotically fast because of the uniform distribution of elements.

The limitations of bucket sort are –

- It may or may not be a stable sorting algorithm.
- It is not useful if we have a large array because it increases the cost.
- It is not an in-place sorting algorithm, because some extra space is required to sort the buckets.

The best and average-case complexity of bucket sort is **O(n + k)**, and the worst-case complexity of bucket sort is **O(n ^{2})**, where

**n**is the number of items.

Bucket sort is commonly used –

- With floating-point values.
- When input is distributed uniformly over a range.

The basic idea to perform the bucket sort is given as follows –

Now, let’s see the algorithm of bucket sort.

### Algorithm

### Scatter-gather approach

We can understand the Bucket sort algorithm via scatter-gather approach. Here, the given elements are first scattered into buckets. After scattering, elements in each bucket are sorted using a stable sorting algorithm. At last, the sorted elements will be gathered in order.

Let’s take an unsorted array to understand the process of bucket sort. It will be easier to understand the bucket sort via an example.

Let the elements of array are –

Now, create buckets with a range from 0 to 25. The buckets range are 0-5, 5-10, 10-15, 15-20, 20-25. Elements are inserted in the buckets according to the bucket range. Suppose the value of an item is 16, so it will be inserted in the bucket with the range 15-20. Similarly, every item of the array will insert accordingly.

This phase is known to be the **scattering of array elements**.

Now, **sort** each bucket individually. The elements of each bucket can be sorted by using any of the stable sorting algorithms.

At last, **gather** the sorted elements from each bucket in order

Now, the array is completely sorted.

## Bucket sort complexity

Now, let’s see the time complexity of bucket sort in best case, average case, and in worst case. We will also see the space complexity of the bucket sort.

### 1. Time Complexity

Case | Time | Complexity |
---|---|---|

Best Case | O(n + k) | |

Average Case | O(n + k) | |

Worst Case | O(n^{2}) |

**Best Case Complexity –**It occurs when there is no sorting required, i.e. the array is already sorted. In Bucket sort, best case occurs when the elements are uniformly distributed in the buckets. The complexity will be better if the elements are already sorted in the buckets.

If we use the insertion sort to sort the bucket elements, the overall complexity will be linear, i.e., O(n + k), where O(n) is for making the buckets, and O(k) is for sorting the bucket elements using algorithms with linear time complexity at best case.

The best-case time complexity of bucket sort is**O(n + k)**.**Average Case Complexity –**It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. Bucket sort runs in the linear time, even when the elements are uniformly distributed. The average case time complexity of bucket sort is**O(n + K)**.**Worst Case Complexity –**In bucket sort, worst case occurs when the elements are of the close range in the array, because of that, they have to be placed in the same bucket. So, some buckets have more number of elements than others.

The complexity will get worse when the elements are in the reverse order.

The worst-case time complexity of bucket sort is**O(n**.^{2})

### 2. Space Complexity

Space Complexity | O(n*k) |

Stable | YES |

- The space complexity of bucket sort is O(n*k).

## Implementation of bucket sort

Now, let’s see the programs of bucket sort in different programming languages.

**Program:** Write a program to implement bucket sort in C language.

**Output**

After the execution of above code, the output will be –

**Program:** Write a program to implement bucket sort in C++.

**Output**

After the execution of above code, the output will be –

**Program:** Write a program to implement bucket sort in C#.

**Output**

After the execution of above code, the output will be –

**Program:** Write a program to implement bucket sort in Java.

**Output**

After the execution of above code, the output will be –

So, that’s all about the article. Hope the article will be helpful and informative to you.

This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.