Bucket Sort in Java

Introduction

This tutorial explains the Bucket Sort Algorithm with an example list of 8 numbers. It then provides the Java implementation of Bucket Sort Algorithm and explains its Big Oh complexity.

What is Bucket Sort

Bucket sort is a sorting algorithm which divides the range of the values to be sorted into a number of equal parts, called buckets. Every item of the list is put into the bucket for the part of the range in which its value lies. Each bucket is then sorted on its own, and finally the buckets are read one after the other, from the bucket for the smallest values to the bucket for the largest values, to get the sorted list.

When every bucket holds only a few items, sorting the buckets is quick. Bucket sort works best when the values are spread evenly, or uniformly distributed, over their range, because then every bucket gets about the same number of items.

Bucket Sort Working Explained

Lets understand the working of Bucket Sort using an example. Lets say the list to be sorted is [42, 32, 73, 25, 67, 94, 12, 38], and all the values lie between 0 and 99. We will use 5 buckets, each of which covers 20 values - bucket 0 holds the values 0 to 19, bucket 1 the values 20 to 39, and so on up to bucket 4, which holds the values 80 to 99.
First step - putting the items into buckets
The list is read from left to right, and every item is added to its bucket. 42 goes to bucket 2, 32 goes to bucket 1, 73 goes to bucket 3, and so on. At the end of this step the buckets are - bucket 0: [12], bucket 1: [32, 25, 38], bucket 2: [42], bucket 3: [73, 67] and bucket 4: [94].

Second step - sorting each bucket
Every bucket is sorted on its own. Buckets 0, 2 and 4 have a single item and are already sorted. Bucket 1 becomes [25, 32, 38] and bucket 3 becomes [67, 73].

Third step - joining the buckets
The buckets are read in order, from bucket 0 to bucket 4, and their items are written back into the list. As all the values in a bucket are smaller than all the values in the next bucket, the list is now sorted - [12, 25, 32, 38, 42, 67, 73, 94].

Bucket sort of the list 42, 32, 73, 25, 67, 94, 12, 38 with 5 buckets of 20 values each - after distributing, the buckets hold 12; 32, 25, 38; 42; 73, 67; and 94; after sorting each bucket and joining them in order, the list is 12, 25, 32, 38, 42, 67, 73, 94
Bucket Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
import java.util.ArrayList;
public class BucketSort {
  static int intArray[] = { 42, 32, 73, 25, 67, 94, 12, 38 };
  static final int BUCKET_COUNT = 5;
  public static void doSort() {
    ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < BUCKET_COUNT; i++) {
      buckets.add(new ArrayList<>());
    }
    for (int i = 0; i < intArray.length; i++) {
      int bucketIndex = intArray[i] * BUCKET_COUNT / 100;
      buckets.get(bucketIndex).add(intArray[i]);
    }
    int position = 0;
    for (ArrayList<Integer> bucket : buckets) {
      insertionSort(bucket);
      for (int value : bucket) {
        intArray[position] = value;
        position++;
      }
    }
  }
  public static void insertionSort(ArrayList<Integer> bucket) {
    for (int outer = 1; outer < bucket.size(); outer++) {
      for (int inner = outer; inner > 0 && bucket.get(inner) < bucket.get(inner - 1); inner--) {
        int temp = bucket.get(inner);
        bucket.set(inner, bucket.get(inner - 1));
        bucket.set(inner - 1, temp);
      }//inner loop ends
    }//outer loop ends
  }
  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }
  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 42 32 73 25 67 94 12 38
Array After Sorting -> 12 25 32 38 42 67 73 94

Explanation of the code

  • The doSort() method in the above java program holds the sorting logic. It follows the 3 steps explained above.
  • The buckets are kept in buckets, an ArrayList of BUCKET_COUNT buckets, where every bucket is itself an ArrayList of values. A list is used for a bucket as the number of items each bucket will get is not known in advance.
  • The bucket of an item is found with intArray[i] * BUCKET_COUNT / 100. For the values 0 to 99 and 5 buckets this gives 0 for the values 0 to 19, 1 for the values 20 to 39, and so on. This program therefore expects all the values to be between 0 and 99.
  • The last loop goes over the buckets in order. Every bucket is sorted by the insertionSort() method, and its items are then written back into the list at position, which is the next position in the list to be written.
  • The insertionSort() method is the Insertion SortClick to read: Insertion Sort algorithm, written for an ArrayList. Insertion sort is the usual choice for sorting the buckets, as it is very fast for lists with just a few items.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.

Big Oh Complexity of Bucket Sort Algorithm

Putting n items into k buckets and joining the buckets again takes O(n + k) time. The time taken to sort the buckets depends on how the items are spread over the buckets -
  • Average case - when the values are uniformly distributed, every bucket gets only a few items, and sorting all the buckets takes about O(n) time. The average complexity of bucket sort is thus O(n + k).
  • Worst case - when all the values fall into the same bucket, that one bucket holds the whole list, and insertion sort makes the complexity O(n2).
  • Space - the buckets hold a copy of all the items, so bucket sort needs O(n + k) extra space, unlike in-place sorts such as insertion sort or Shell SortClick to read tutorial: Shell Sort in Java.
Bucket sort is closely related to Counting SortClick to read tutorial: Counting Sort in Java. Counting sort is like a bucket sort with one bucket for every possible value, where a bucket only needs to remember how many items it got.

Summary

In this tutorial on bucket sort algorithm in java we understood how the algorithm sorts by distributing the items into buckets which cover equal parts of the range of values, went through a step-by-step walkthrough of sorting an 8-number list using 5 buckets, saw the java code for implementing bucket sort along with its explanation, and finally understood its Big Oh complexity in the average and the worst case.