Bucket Sort
Bucket sort
Bucket sort extends counting sort. A count slot can be viewed as a bucket for one value, while an interval bucket holds values from a range.
Divide values into equal-width intervals, sort each interval's contents, and combine them. A roughly even distribution helps efficiency. If all data enters one bucket, the distribution advantage disappears and performance depends on the within-bucket sorting method.
For example:
Bucket sort: distribute, compare within buckets, gather
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Choose bucket intervals and distribute the sequence into them:
Sort within each bucket:
Gather the buckets back into the original array in order:
Bucket count depends on the data range. A common choice uses as many buckets as items. The integer sample below uses width:
Bucket sort
#include <stdio.h>
#include <stdlib.h>
typedef int T;
static int cmp(const void *a, const void *b) {
return (*(const T *)a > *(const T *)b) - (*(const T *)a < *(const T *)b);
}
T *bucket_sort(T *arr, int n) {
if (n == 0) {
return arr;
}
T max_val = arr[0];
T min_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
if (arr[i] < min_val) {
min_val = arr[i];
}
}
int bucket_size = (max_val - min_val) / n + 1;
T **buckets = (T **)malloc(n * sizeof(T *));
for (int i = 0; i < n; i++) {
buckets[i] = (T *)calloc(n + 1, sizeof(T));
}
for (int i = 0; i < n; i++) {
int index = (arr[i] - min_val) / bucket_size;
buckets[index][0]++;
buckets[index][buckets[index][0]] = arr[i];
}
for (int i = 0; i < n; i++) {
qsort(buckets[i] + 1, buckets[i][0], sizeof(T), cmp);
}
int i = 0;
for (int j = 0; j < n; j++) {
for (int k = 1; k <= buckets[j][0]; k++) {
arr[i++] = buckets[j][k];
}
}
for (int i = 0; i < n; i++) {
free(buckets[i]);
}
free(buckets);
return arr;
}
int main() {
int arr[] = {18, 11, 28, 45, 23, 49};
int n = sizeof(arr) / sizeof(arr[0]);
bucket_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}The Lab uses four buckets of width ten; the code uses n buckets. Both partitions can sort correctly. The C sample reserves n values for every bucket, using extra space. Within-bucket comparison sorting means total time is not unconditionally .
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Bucket contents still need sorting
Distribute [37,12,29,14,32,21] into [10,20), [20,30), [30,40). Record each placement, each bucket before and after sorting, and the gathered result. Use these intervals only.