Bucket sort implementation in Java

May 05, 2024

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.
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