Sorting algorithm is very useful when it comes to a competitive coding and practice for interviews. It is the heart of computing and choosing the right sorting algorithms can create difference in performance.
It is an important part of many computer programs that helps in organizing data in a way that makes it easier. Instead of comparing every number with every other one. Bucket Sort groups the numbers into small sections called buckets.
Then it sorts the numbers inside each bucket and puts them all together at the end. This makes the sorting faster when the data fits certain conditions. In this blog we will talk about how bucket sort algorithm works from other algorithms like Quick Sort, Merge Sort and so on. In the end we will also have conversation about the real world applications of bucket sort algorithms.
What is Bucket Sort Algorithm?
Bucket Sort is a way to sort numbers by putting them into small groups called buckets. Each bucket holds numbers that are close in value. After this, we sort the numbers inside each bucket. Then we join all the buckets to get the final sorted list.
This method works well when the numbers are spread out evenly in a fixed range. It does not compare numbers directly like bubble sort or quick sort. Instead, it places them in the right bucket and sorts inside that group.
Bucket Sort is often used to sort decimal numbers like values between 0 and 1. It is simple and fast when used for the right kind of data.
def bucket_sort(arr):
if len(arr) == 0:
return arr
bucket_count = len(arr)
buckets = [[] for _ in range(bucket_count)]
for num in arr:
index = int(num * bucket_count)
if index == bucket_count:
index = bucket_count - 1
buckets[index].append(num)
for bucket in buckets:
bucket.sort()
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(bucket)
return sorted_arr
data = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]
sorted_data = bucket_sort(data)
print("Sorted array:", sorted_data)
How Bucket Sort Algorithm Works?
There are several steps where we will able to understand how bucket sort algorithm works.
- Create a few empty buckets to hold the numbers. The number of buckets depends on how many numbers you have or the range of the numbers.
- Look at each number and place it in the right bucket based on its value.
- Sort the numbers inside each bucket. Since buckets have fewer numbers, this is easy.
- Take the sorted buckets and put them together to get the final sorted list.
Suppose you have this list of numbers to sort:
[0.3, 0.1, 0.7, 0.4, 0.6, 0.2]
- Step 1: Make 3 empty buckets
- Step 2: Put numbers into buckets based on value:
- Bucket 1: [0.1, 0.2, 0.3]
- Bucket 2: [0.4, 0.6]
- Bucket 3: [0.7]
- Step 3: Sort each bucket (they are already sorted here)
- Step 4: Join buckets:
[0.1, 0.2, 0.3, 0.4, 0.6, 0.7]
This is the sorted list using the bucket sorting algorithm.
Time and Space Complexity of Bucket Sort
| Case | Time Complexity |
| Best Case | O(n + k) |
| Average Case | O(n + k) |
| Worst Case | O(n²) (when all elements go to the same bucket) |
The above table represents the time and space complexity that is O(n+k) where n represents the number of elements and k represents the number of buckets.
Implementation of Bucket Sort Algorithm in Python
def bucket_sort(arr):
if len(arr) == 0:
return arr
bucket_count = len(arr)
buckets = [[] for _ in range(bucket_count)]
for num in arr:
index = int(num * bucket_count)
if index == bucket_count:
index = bucket_count - 1
buckets[index].append(num)
for bucket in buckets:
bucket.sort()
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(bucket)
return sorted_arr
# Example usage
data = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]
sorted_data = bucket_sort(data)
print("Sorted array:", sorted_data)
This code is for sorting numbers using the bucket sort method. First, it checks if the list is empty. If yes, it returns the list as it is. Then it makes a number of empty buckets equal to how many numbers are in the list.
It goes through each number and puts it into the right bucket based on its value. If the number ends up outside the last bucket, it moves it back inside. After placing all the numbers into buckets, it sorts each bucket separately.
Since each bucket has only a few numbers, sorting is fast. Finally, it joins all the buckets together into one list and returns the sorted result. So, it breaks the big sorting problem into smaller ones and solves them easily.
Comparison of Bucket Sort with Quick and Merge Sort
| Thing | Bucket Sort | Quick Sort | Merge Sort |
| Fastest Time | Very fast if numbers spread | Usually fast but depends | Always fast same speed |
| Slowest Time | Very slow if all in one box | Very slow if bad picking | Always same slow but steady |
| Keeps Order Same? | Yes if inside sort is good | No | Yes |
| Uses Extra Space? | Yes, needs buckets | No, sorts in place | Yes, needs extra space |
| Best For | Numbers spread evenly | Any list but pick pivot well | When order matters or big list |
| Easy to Understand | Medium, need buckets idea | Hard, need to pick pivot | Easy, just split and join |
Applications of Bucket Sort Algorithm
- Bucket sort is used to sort student marks when they are decimal numbers. It puts them in small boxes and arranges them easily.
- In online games it helps sort player scores fast. It shows who is first second and last very quickly.
- It is used in making charts when numbers are between 0 and 1. It keeps the data clean and sorted for display.
- Machines like sensors give small values often. Bucket sort helps to keep those values in order fast.
- It is good when new numbers keep coming and need sorting. If they are spread out evenly bucket sort works really well.
Advantages of Bucket Sort Algorithm
- Bucket sort is very fast when numbers are spread out evenly. It just puts them in the right box and sorts them quickly.
- It works well with decimal numbers between 0 and 1. This makes it perfect for special cases like scores or rates.
- It uses simple sorting inside buckets like insertion sort. That means it’s easy to combine two simple methods.
- When data is already kind of sorted it becomes super fast. It hardly needs to do any work.
- It gives better speed than many other sorts in the best case. This saves time when working with large inputs.