Updated March 30, 2023
Definition of Bucket Sort Algorithm
Bucket Sort is a sorting technique that works on an algorithm that takes an unsorted array as input and returns an array of sorted elements. The working principle of bucket sort is to divide the given series of numbers into several buckets, sort the data in each bucket according to the requirement, and then merge the data again that outputs an array of sorted elements.
Bucket Sort follows the Scatter-order-gather approach since the elements are scattered first into the respective buckets and are then sorted in the bucket and gathered to form a sorted array as the final step.
How Does Bucket Sort Work?
- Let us take an input array of 7 elements.
The input array is:
| 0.54 | 0.44 | 0.45 | 0.64 | 0.49 | 0.59 | 0.10 |
- Create an empty array of size 10, as shown below. Each slot of this list or array is to use as a bucket for storing elements.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
- Now, we have to insert the elements in their respective buckets according to the bucket range.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
For example, In our code, we have buckets with ranges as shown in the below figure:
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
The bucket-1 range varies from 0 to 1, bucket-2 from 1 to 2, and bucket n from (n-1) to n. To insert elements in the respective buckets, follow the following three steps:
- Let us take an element from the input array as an example that is 0.54
- Multiply it by the size of the empty array(size = 10) and convert the result to an integer using int(). You will get:
0.54 × 10 = 5.4
On converting it to integer, we get, int(5.4) = 5
- Finally, 5.4 is inserted into bucket-5
| 0.54 | 0.44 | 0.45 | 0.64 | 0.49 | 0.59 | 0.10 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 0 | 0 | 0 | 0.54
0.59 |
0 | 0 | 0 | 0 |
Similarly, 0.59 is also inserted into the same bucket, bucket-5, because the two elements’ floor value is equal.
The above process continues until all the elements settle in their respective buckets.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0.10
|
0 | 0 | 0 | 0.44
0.45 0.49 |
0.54
0.59 |
0.64
|
0 | 0 | 0 |
- The elements of each bucket are then sorted using any of the algorithm techniques. In this code, the default sorting technique is used by using the sorted() function, which uses the Timsort algorithm.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0.10
|
0 | 0 | 0 | 0.44
0.45 0.49 |
0.54
0.59 |
0.64
|
0 | 0 | 0 |
- Finally, the elements from the buckets have been gathered by passing the elements into the original array by iteration.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0.10
|
0 | 0 | 0 | 0.44
0.45 0.49 |
0.54
0.59 |
0.64
|
0 | 0 | 0 |
| 0.10 | 0.44 | 0.45 | 0.49 | 0.54 | 0.59 | 0.64 |
Bucket Sort Algorithm
Before moving on to the actual implementation of bucket sort, let’s walk through the algorithm steps.
- Step 1: Create a list, each of which can hold another list known as a bucket in it.
- Step 2: Initialize the bucket to 0 values.
- Step 3: Put all the elements into the buckets by matching the bucket range with the floor value of the respective element.
- Step 4: sort elements in each bucket using any of the sorting algorithms.
- Step 5: Gather elements from each bucket.
Source Code in Python
BucketSort.py
# Bucket Sort in Python
def BucketSort(array):
buckets_list = []
# 1. Create empty buckets in buckets list(buckets_list)
for i in range(len(array)):
buckets_list.append([])
# 2. Insert elements into their respective buckets
for j in array:
index_b = int(10 * j)
buckets_list[index_b].append(j)
# 3. Sort the elements of each bucket
for i in range(len(array)):
buckets_list[i] = sorted(buckets_list[i])
# 4. Get the sorted elements
new_array = []
for i in range(len(array)):
for j in range(len(buckets_list[i])):
for k in range(len(array)):
new_array.append(buckets_list[i][j])
break
return new_array
array = [.54, .44, .45, .64, .49, .59, .10]
print("Sorted Array in ascending order is: ")
print(BucketSort(array))Output:
Time Complexity of Bucket Sort
- Worst-case complexity: In General, one bucket contains many elements when there are elements of the normal range, But when there are elements of the very close range, they are more likely to fall in the same bucket. So, in this case, more elements get placed in the same bucket resulting in more number elements in some buckets than others. The algorithm complexity depends on the number of elements in the bucket and, it becomes even worse when the elements in the bucket are in reverse order. When insertion sort is used to sort the elements then the time complexity will be O(n2)
- Best case complexity: Best case complexity occurs when there are an equal number of elements in the buckets and, it will be even better if the elements inside the buckets are already sorted. Suppose insertion sort is used to sort the elements in the buckets. In that case, the overall best case complexity will be O(n+k), where O(n) is the complexity for making the buckets and O(k) is the complexity for sorting the elements in the buckets.
- Average case complexity: Average case complexity occurs when the elements are distributed randomly in the array of buckets. In general, Bucket sort runs in linear time in all cases until the sum of the squares of the bucket sizes is linear in the total number of elements. Finally, this makes O(n) to be the average-case complexity of the bucket sort algorithm.
Limitations of Bucket Sort Algorithm
Limitations of the bucket sort algorithm are given below:
- You cannot apply the bucket sort algorithm to all the data types since it takes a slightly different process for each data type.
- Bucket sort occupies more space since you require separate memory to store elements in each bucket and an array to store these buckets.
- The bucket sort algorithm depends on the distribution of input values. The range of the input values also decides the efficiency of this algorithm. So if the input values are tightly clustered, this algorithm is not worth it.
- Each bucket in the array needs to be of the same size to handle the worst-case scenario. If the bucket is not of the same size as the array size, this algorithm fails for the worst-case scenario.
Conclusion
- Bucket Sort is a sorting technique that works on an algorithm that takes an unsorted array as input and returns an array of sorted elements.
- Bucket Sort follows the Scatter-order-gather approach since it sorts the elements by first scattering them and gathering them again by obtaining the sorted order.
- Multiplying the element with the array size and converting it to an integer from float gives the bucket number.
Recommended Articles
This is a guide to Bucket Sort Algorithm. Here we also discuss the definition and how does bucket sort work? Along with the time complexity of bucket sort. You may also have a look at the following articles to learn more –
