Bucket Sort
Bucket sort distributes elements into a number of buckets, sorts each bucket individually (using another sorting algorithm, often insertion sort), then concatenates the buckets. It works well when input is uniformly distributed. Average O(n + k), worst O(n²).
Java implementation (for floating point numbers between 0 and 1):
public static void bucketSort(float[] arr) {
int n = arr.length;
List[] buckets = new ArrayList[n];
for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>();
for (float num : arr) {
int idx = (int) (num * n);
buckets[idx].add(num);
}
for (List bucket : buckets) {
Collections.sort(bucket);
}
int index = 0;
for (List bucket : buckets) {
for (float val : bucket) {
arr[index++] = val;
}
}
}
Two Minute Drill
- Bucket sort distributes elements into buckets, sorts each, then concatenates.
- Average O(n + k), worst O(n²) (if many elements in one bucket).
- Useful for uniformly distributed data.
- Often combined with insertion sort for small buckets.
Need more clarification?
Drop us an email at career@quipoinfotech.com