Bucket Sort: A Comprehensive Guide
Introduction to Bucket Sort
Bucket sort, sometimes referred to as bin sort, is a distribution sort algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying the bucket sort algorithm. Bucket sort is mainly useful when the input is uniformly distributed over a range.
How Bucket Sort works?
Step-by-step:
- Determine the Number of Buckets: First, you need to decide the number of buckets you want to use. This number can be the default value or can be derived from the input data.
- Place Elements in Buckets: Go through the input data and place each element into its corresponding bucket. This distribution is based on the range and number of buckets.
- Sort Buckets Individually: Once all elements are placed in their respective buckets, sort each bucket. This can be done using any sorting algorithm, but usually, insertion sort is used for this purpose due to its efficiency with small data sizes.
- Concatenate Buckets: Finally, gather elements from the buckets in order and get the sorted array.
Performance of Bucket Sort
- Average Time Complexity: O(n + k), where
n
is the number of elements, andk
is the number of buckets. - Worst Time Complexity: O(n^2), when all elements are placed in a single bucket.
- Space Complexity: O(n * k)
Use Cases
Bucket sort is efficient when:
- The distribution of input values is somewhat uniform.
- There’s a range of input data, and this range isn’t much larger than the number of elements.
- When the internal sort is efficient at handling small data sizes.
Limitations
- Bucket sort isn’t suitable for sequences of widely varying sizes since some buckets may have many more elements than others.
- It’s not adaptive. Even if the input is partially sorted, bucket sort will still process it fully.
Example in JavaScript:
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) {
return arr;
}
// Determine min and max values
let minValue = arr[0];
let maxValue = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// Create buckets
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
const allBuckets = new Array(bucketCount);
for (let i = 0; i < allBuckets.length; i++) {
allBuckets[i] = [];
}
// Push elements into buckets
arr.forEach((currentVal) => {
allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
});
// Sort buckets and gather them in order
return allBuckets.reduce((sortedArray, currentBucket) => {
return sortedArray.concat(currentBucket.sort((a, b) => a - b));
}, []);
}
const sortedArray = bucketSort([3.6, 0.5, 2.7, 5.1, 1.2, 3.3]);
console.log(sortedArray); // [0.5, 1.2, 2.7, 3.3, 3.6, 5.1]
Conclusion
Bucket sort offers a unique approach to sorting by using the distribution of elements. For specific types of input distributions, it can be highly efficient and is worth considering in scenarios where its strengths can be leveraged. However, like all algorithms, it’s essential to understand its advantages and limitations fully.