I. In-Class Exercises

Programming Exercises

(None yet)

II. Knowledge Summary

Core Idea

Bucket Sort is a non-comparison sorting algorithm. Its core idea is: distribute elements to be sorted into several "buckets" according to some mapping rule, sort each bucket individually, and then collect elements in bucket order.

When data is distributed relatively uniformly, bucket sort can achieve O(n) time complexity, breaking through the O(n log n) lower bound of comparison-based sorting.

Prerequisite: The data range must be known, and the data distribution should be relatively uniform.

Algorithm Principle

1. Determine the number and range of buckets: Based on the maximum and minimum values of the data, divide into several equal-width buckets
2. Distribute: Traverse the array and place each element into the corresponding bucket
3. Sort within buckets: Sort the elements within each bucket (any sorting algorithm can be used)
4. Collect: Take out all elements in bucket order

Code Implementation

Integer Bucket Sort (Counting Sort Style)

When the data range is not large (e.g., 0 ~ 10^6), array indices can be used directly as buckets:

1#include <bits/stdc++.h>
2using namespace std;
3
4int cnt[1000001]; // Count of occurrences for each value
5
6int main() {
7    int n;
8    scanf("%d", &n);
9    int a[100005];
10    int maxVal = 0;
11    for (int i = 0; i < n; i++) {
12        scanf("%d", &a[i]);
13        cnt[a[i]]++;
14        maxVal = max(maxVal, a[i]);
15    }
16
17    // Collect in bucket order
18    int idx = 0;
19    for (int v = 0; v <= maxVal; v++) {
20        while (cnt[v] > 0) {
21            a[idx++] = v;
22            cnt[v]--;
23        }
24    }
25
26    for (int i = 0; i < n; i++) printf("%d ", a[i]);
27    return 0;
28}

General Bucket Sort (Floating Point / Large Range)

When the data range is large or involves floating point numbers, use multiple buckets for segmentation:

1#include <bits/stdc++.h>
2using namespace std;
3
4void bucketSort(vector<double>& a) {
5    int n = a.size();
6    if (n <= 1) return;
7
8    // Find the maximum and minimum values
9    double minVal = *min_element(a.begin(), a.end());
10    double maxVal = *max_element(a.begin(), a.end());
11
12    // Create n buckets
13    int bucketCount = n;
14    double bucketRange = (maxVal - minVal) / bucketCount + 1e-9;
15    vector<vector<double>> buckets(bucketCount);
16
17    // Distribute elements into buckets
18    for (double x : a) {
19        int idx = (int)((x - minVal) / bucketRange);
20        if (idx >= bucketCount) idx = bucketCount - 1;
21        buckets[idx].push_back(x);
22    }
23
24    // Sort within each bucket
25    for (auto& bucket : buckets) {
26        sort(bucket.begin(), bucket.end());
27    }
28
29    // Collect results
30    int k = 0;
31    for (auto& bucket : buckets) {
32        for (double x : bucket) {
33            a[k++] = x;
34        }
35    }
36}
37
38int main() {
39    vector<double> a = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
40    bucketSort(a);
41    for (double x : a) printf("%.2f ", x);
42    // Output: 0.23 0.25 0.32 0.42 0.47 0.51 0.52
43    return 0;
44}

Execution Example

Using [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51] (7 elements) with 5 buckets:

Bucket range division (0.23 ~ 0.52, each bucket width approximately 0.06):

Collected in bucket order: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

Detailed Problem-Solving Steps

Determine whether bucket sort is appropriate:

1. Data range is known and finite: The maximum and minimum values can be determined
2. Data is relatively uniformly distributed: If data is heavily concentrated in one range, bucket sort degrades
3. Need linear time sorting: When O(n log n) is not fast enough

Variants of bucket sort:

• Counting sort: Number of buckets = size of value range, each bucket holds at most one type of value. Suitable for integers with a small value range.
• Radix sort: Multiple passes of bucket sort, each pass distributing by one digit (ones, tens...).

Application scenarios in competitions:

• Sorting with a small data range (e.g., scores 0~100)
• Sorting by frequency after frequency counting
• Need O(n) sorting to reduce overall complexity

Common Mistakes

1. Unreasonable number of buckets: Too few buckets means too many elements per bucket, degrading to O(n log n); too many buckets wastes space
2. Incorrect bucket boundary calculation: The maximum value element may go out of bounds and needs special handling
3. Ignoring data distribution: When data is extremely non-uniform (e.g., 1, 1, 1, ..., 1000000), bucket sort performs poorly
4. Forgetting to handle empty buckets: Forgetting to skip empty buckets during collection
5. Floating point precision issues: Floating point errors when calculating bucket indices leading to incorrect distribution

Algorithm Evaluation

Comparison with comparison-based sorting:

Bucket sort breaks through the O(n log n) sorting lower bound, but the cost is additional space and prior knowledge about the data. In competitions, bucket sort often appears in the form of "counting sort," used for scenarios with small value ranges.