Bucket Sort
A distribution-based sorting algorithm that divides elements into buckets, sorts each bucket individually, and then concatenates them.
Visualization
Details
Analogy
Imagine sorting a deck of playing cards. You first create 4 buckets (one for each suit: hearts, diamonds, clubs, spades), distribute the cards into their respective suit buckets, sort each bucket individually by rank, and finally combine all sorted buckets. This is much faster than comparing every card with every other card.
Purpose
To efficiently sort uniformly distributed data by dividing it into buckets, sorting each bucket, and combining the results. This approach is particularly effective when input values are uniformly distributed across a range.
Use Cases
Ideal for sorting floating-point numbers uniformly distributed between 0 and 1, or sorting data when the distribution is known and relatively uniform. Commonly used in parallel sorting algorithms and external sorting. Works well with large datasets when input distribution is predictable.
Algorithm Steps
function bucketSort(array):
n = length(array)
buckets = create n empty buckets
for i = 0 to n - 1:
index = floor(n * array[i] / (max + 1))
insert array[i] into buckets[index]
for i = 0 to n - 1:
sort each bucket using insertion sort
result = concatenate all buckets
return result
Explanation
What's Happening?
Initial array with 6 elements: [7, 2, 9, 4, 1, 6]. We'll distribute these into buckets based on their values.
Code Implementation
def bucket_sort(arr):
if len(arr) == 0:
return arr
# Find maximum value to normalize
max_val = max(arr)
min_val = min(arr)
bucket_range = (max_val - min_val) / len(arr)
# Create empty buckets
buckets = [[] for _ in range(len(arr))]
# Distribute elements into buckets
for num in arr:
if bucket_range == 0:
index = 0
else:
index = int((num - min_val) / bucket_range)
if index == len(arr):
index -= 1
buckets[index].append(num)
# Sort individual buckets and concatenate
result = []
for bucket in buckets:
result.extend(sorted(bucket))
return result