AIOJ

This page briefly introduces bucket sort.

Definition

Bucket sort is a sorting algorithm suitable for data whose value range is large but whose distribution is relatively uniform.

Process

Bucket sort proceeds as follows:

Allocate a fixed-size array as a set of empty buckets;
Traverse the sequence and place each element into its corresponding bucket;
Sort every nonempty bucket;
Put the elements from the nonempty buckets back into the original sequence.

Properties

Stability

If the sorting algorithm used inside each bucket is stable, and inserting elements into buckets preserves their relative order, then bucket sort is stable.

Because each bucket usually contains only a few elements, insertion sort is commonly used. In that case, bucket sort is stable.

Time complexity

The average time complexity of bucket sort is $O(n + n^2/k + k)$ (partitioning the value range into $n$ buckets on average, sorting, and merging the elements again). When $k\approx n$ , it is $O(n)$ . ¹

The worst-case time complexity of bucket sort is $O(n^2)$ .

Implementation

C++

constexpr int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

Python

N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]

def insertion_sort(A):
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key

def bucket_sort():
    bucket_size = int(w / n + 1)
    for i in range(0, n):
        bucket[i].clear()
    for i in range(1, n + 1):
        bucket[int(a[i] / bucket_size)].append(a[i])
    p = 0
    for i in range(0, n):
        insertion_sort(bucket[i])
        for j in range(0, len(bucket[i])):
            a[p] = bucket[i][j]
            p += 1

References and notes

Footnotes

Bucket sort - Wikipedia ↩

Bucket Sort