Bucket sort implementation in Java

Bucket Sort in Java

In this article we will go though a simple implementation of Bucket sort in Java

What is Bucket sort

Bucket sort is a sorting algorithm that divides the inputs into several buckets. Once the buckets are populated with input data, then all these buckets are sorted individually using a different sorting mechanism. After individual buckets are sorted they are contaminated together and returned as 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 the concatenation of buckets[0] .....buckets[k]
Bucket sort implementation in java.
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 i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");

    }
  }

  public static void bucketSort(int[] arr, int numBuckets) {

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

    }

    distributeToBuckets(arr, numBuckets, buckets);

    // sort the elements in each bucket
    for (ArrayList<Integer> bucket : buckets) {
      Collections.sort(bucket);
    }

    // concatenate the elements in each bucket to obtain the sorted array
    int index = 0;
    for (ArrayList<Integer> bucket : buckets) {
      for (int item : bucket) {
        arr[index++] = item;

      }

    }

  }

  private static void distributeToBuckets(int[] arr, int numBuckets,
      ArrayList<ArrayList<Integer>> buckets) {
    // determine minimum and maximum values of input array
    int min = Arrays.stream(arr).min().getAsInt();
    int max = Arrays.stream(arr).max().getAsInt();
    float diff = max - min;
    float divisor = diff / (numBuckets - 1);

    // place elements into buckets based on value
    for (int i = 0; i < arr.length; i++) {
      int index = (int) ((arr[i] - min) / divisor);
      buckets.get(index).add(arr[i]);

    }
  }

}

Complexity

The best case for bucket sort happens when the data can be distributed evenly across the buckets. These leads to a situation when non of the buckets are overloaded. This uniform distribution minimizes the complexity of sorting each bucket, leading to an overall time complexity of O(n+k), where n represents the number of elements and k refers to the number of buckets Best Case Complexity : O(n+k)
Average Case Complexity : O(n+k)
Worst Case complexity: O(n²)
Space complexity : O(n+k)

Summary

Bucket sort is a unique sorting method where the inputs are distributed in individual buckets and then the buckets are sorted using other sorting mechanism.

No comments :

Post a Comment

Please leave your message queries or suggetions.