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

How to Sort HashMap in java

April 28, 2020

How to Sort HashMap in java

This article covers some of the aspects of sorting Map in Java. Java Map comes in different flavours, like HashMap, TreeMap, LinkedHashMap etc. TreeMap for instance will sort the data based on the keys. We can also pass a custom Comparator to sort based on the keys as per the custom sort algorithm.
We can have two requirements in terms of sorting, first one is sorting by Keys and second is Sorting by Values. Following examples demonstrates few approaches for sorting by key and sorting by value. Following examples uses Java Lambda and Stream api to sort Java HashMap instance.

Sort by Value

Map sort by value in revere order
Following code snippet sorts the map based on value in reverse order and populates a new map reverseSortedMap from the data.
//LinkedHashMap preserve the ordering of elements in which they are inserted
Map reverseSortedMap =  new LinkedHashMap();
//Use Comparator.reverseOrder() for reverse ordering
map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) 
    .forEachOrdered(x -> reverseSortedMap.put(x.getKey(), x.getValue()));

Sort By Key

Map sort by key in revere order
Following code snippet sorts the map based on the keys in reverse order.
//LinkedHashMap preserve the ordering of elements in which they are inserted
Map reverseSortedMapByKey =  new LinkedHashMap();;
//Use Comparator.reverseOrder() for reverse ordering
map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder())) 
    .forEachOrdered(x -> reverseSortedMapByKey.put(x.getKey(), x.getValue()));
 

System.out.println("Sorted by Value Map : " + reverseSortedMapByKey);

Full Example

MapSortJava
public class MapSortJava {

  public static void main(String[] args) {

    Map<Integer, String> map = new HashMap<Integer, String>();
    map.put(101, "Tokyo");
    map.put(3, "New York");
    map.put(2, "San Francisco");
    map.put(14, "Los Angels");
    map.put(5, "Austin");

    System.out.println("Unsorted Map : " + map);
    
   // LinkedHashMap preserve the ordering of elements in which they are inserted
    Map<Integer, String> reverseSortedMap = new LinkedHashMap<Integer, String>();;
    // Use Comparator.reverseOrder() for reverse ordering
    map.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .forEachOrdered(x -> reverseSortedMap.put(x.getKey(), x.getValue()));
    System.out.println("Sorted by Value Map : " + reverseSortedMap);


    // LinkedHashMap preserve the ordering of elements in which they are inserted
    Map<Integer, String> reverseSortedMapByKey = new LinkedHashMap<Integer, String>();;
    // Use Comparator.reverseOrder() for reverse ordering
    map.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
        .forEachOrdered(x -> reverseSortedMapByKey.put(x.getKey(), x.getValue()));
    System.out.println("Sorted by Value Map : " + reverseSortedMapByKey);

  }
}
Output
Unsorted Map : 2 ==> San Francisco 3 ==> New York 101 ==> Tokyo 5 ==> Austin 14 ==> Los Angels Sorted by Value Map (Reverse) : 2 ==> San Francisco 3 ==> New York 101 ==> Tokyo 5 ==> Austin 14 ==> Los Angels Sorted by Value Map (Reverse) : 101 ==> Tokyo 14 ==> Los Angels 5 ==> Austin 3 ==> New York 2 ==> San Francisco
Summary of steps
  • Get the entry set by calling the Map.entrySet().
  • Get the entry set stream by calling stream() method.
  • Use the Map.Entry.comparingByValue() or Map.Entry.comparingByKey().
  • Call the sorted method with a Comparator.
  • call the terminal operation forEachOrdered to store the each entries in the new Map.
Read More