Bucket Sort

1. Bucket Sort Algorithm
2. Bucket Sort Example
3. Bucket Sort Algorithm Implementation
4. Bucket Sort Algorithm Complexity

Bucket Sort is a comparison type sorting algorithm. It sorts elements by distributing them into buckets or bins and using a different algorithm (usually insertion sort) to sort individual buckets’ content. The individual sorted buckets are then appended together to get the final sorted array. This approach of sorting algorithm is also known as the scatter-gather approach. It is mainly used when the input is uniformly distributed over a range like floats ranging from 0.00 to 1.00.

Bucket Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

Bucket Sort Example

Suppose we have the array: (0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). We will sort it using the bucket sort algorithm.

• Make 10 buckets each of range 0.1.

• After inserting elements into buckets we get:

• Sort individual buckets to get:

Appending all the results together, we get the final sorted array as: (0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55).

Bucket Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Bucket Sort Algorithm Complexity

Time Complexity

• Average Case

The average case occurs if elements are randomly distributed, and the algorithm gives very efficient results. The time complexity is of the order of [Big Theta]: O(n+k). It is one of the few algorithms with average linear time complexity, and this complexity holds if the sum of the squares of the bucket sizes is linear in n.

• Worst Case

The worst-case occurs when many elements are in close range in the array and get clustered together in the same bucket. It takes away all the advantages of dividing inputs into buckets, and the total complexity becomes dependent on the sorting algorithm used. Insertion sort has a worst-case time complexity of O(n²) when the elements are in reversed order. Hence, the worst-case time complexity is [Big O]: O(n²).

• Best Case

The best-case occurs when the elements are uniformly distributed in all the buckets, or we get an already sorted array. Total time complexity comprises the time required to create buckets O(n) and the time required to sort O(k). The best-case time complexity is [Big Omega]: O(n+k).

Space Complexity

The worst-case space complexity for the bucket sort algorithm is O(n*k), where n is the number of elements and k is the number of buckets. Space complexity can be reduced to O(n+k) by reducing the space to hold all elements and storing pointers to the start the bucket.