Bucket sort implementation in Java

May 05, 2024

Bucket Sort in Java

In this article we will go through a simple implementation of Bucket Sort in Java.

What is Bucket Sort

Bucket Sort is a sorting algorithm that divides the input into several buckets. Once the buckets are populated with input data, they are sorted individually using another sorting mechanism. After sorting, the buckets are concatenated together to produce the final result.
Following is the pseudocode for Bucket Sort: 
function bucketSort(array, k) is 
  buckets ← new array of k empty lists
  Max ← the maximum key value in the array
  Min ← the minimum key value in the array 
  Divisor ← (Max - Min) / (k - 1)

  for i = 0 to length(array) do
    insert array[i] into buckets[floor((array[i] - Min) / Divisor)]

  for i = 0 to k do
    Sort(buckets[i]) 

  return concatenation of buckets[0] ... buckets[k]
Bucket Sort implementation in Java: 
import java.util.*;

public class BucketSortExample {

  public static void main(String[] args) {
    int[] arr = {8, 4, 2, 10, 3, 1, 9, 6, 5, 7};
    int numBuckets = 5;
    bucketSort(arr, numBuckets);

    System.out.println("Sorted array:");
    for (int value : arr) {
      System.out.print(value + " ");
    }
  }

  public static void bucketSort(int[] arr, int numBuckets) {
    if (numBuckets <= 0) return;

    // create empty buckets
    ArrayList> buckets = new ArrayList<>(numBuckets);
    for (int i = 0; i < numBuckets; i++) {
      buckets.add(new ArrayList<>());
    }

    distributeToBuckets(arr, numBuckets, buckets);

    // sort each bucket
    for (ArrayList bucket : buckets) {
      Collections.sort(bucket);
    }

    // concatenate
    int index = 0;
    for (ArrayList bucket : buckets) {
      for (int item : bucket) {
        arr[index++] = item;
      }
    }
  }

  private static void distributeToBuckets(int[] arr, int numBuckets,
      ArrayList> buckets) {

    int min = Arrays.stream(arr).min().getAsInt();
    int max = Arrays.stream(arr).max().getAsInt();
    float diff = max - min;
    float divisor = diff / (numBuckets - 1);

    for (int value : arr) {
      int index = (int) ((value - min) / divisor);
      if (index >= numBuckets) index = numBuckets - 1; // safeguard
      buckets.get(index).add(value);
    }
  }
}

Complexity

The best case for Bucket Sort happens when the data is distributed evenly across buckets. This uniform distribution minimizes the sorting inside buckets, leading to overall time complexity:

Best Case: O(n + k)
Average Case: O(n + k)
Worst Case: O(n²)
Space Complexity: O(n + k)

Summary

Bucket Sort is a distribution-based sorting method where input elements are distributed into buckets, and each bucket is sorted using another algorithm. The sorted buckets are then concatenated to form the final sorted output.
Read More