Bucket sort algorithm Java

Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are numerous sorting algorithms available. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space complexity.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java. Today we’re going to look at bucket sort, also known as bin sort.

So far, we have discussed the following:

• Sorting algorithms: Introduction to data sorting
• Bubble sort
• Comb sort
• Big O notation
• Selection sort
• Insertion sort
• Counting sort
• Heap sort
• Merge sort
• Quick sort

Bucket sort definition

Bucket (Bin) sort is a special sorting technique that consists in dividing the elements of the input vector into different groups (buckets or bins). These groups are formed on the basis of a uniform distribution. The groups are then individually sorted by an arbitrary sorting algorithm and the output sorted output is the union of the results of the individual buckets. The computational complexity of the algorithm then depends on the algorithm used to sort individual buckets, the number of buckets created and on how uniformly the values are distributed in the input.

Bucket sort explained

If we need to sort a large amount of data that has the property that it is evenly distributed (e.g. order numbers), by dividing it into subgroups we can reduce the amount of comparisons between elements, which will help us to reduce the sorting time. Once the data is sorted, we can keep it in buckets, and when we add new elements to the buckets, we can sort only the buckets to which the new element has been added. Sorted data is also easier and faster to sort if we use a suitable algorithm, such as insertion sort. Partitioning into multiple buckets also allows us to use parallel sorting and data processing techniques.

The basic principle of the bucket sort algorithm is as follows:

1. Determine bucket count – By analyzing data range once, we can determine the maximum value
2. Create empty buckets (typically using an array of lists)
3. Distribute elements into buckets
   The most appropriate way is to scatter them using a simple hash function.
4. Sort each bucket individually
5. Gather the results from each bucket in the correct order

Bucket sort animation, visualization, gif

Bucket sort advantages

• Relatively efficient for data with a uniform distribution: decimal numbers with a range of 0.0 to 1.0, or integers in a narrow range
• Stable if a stable sorting algorithm is used to sort the data for groups
• It can be parallelized to spread the computational load across multiple processors.

Bucket sort disadvantages

• Requires additional memory space to create buckets
• An inappropriately chosen variance function can significantly increase the time complexity.

Bucket sort time complexity

Variable n = number of array elements, k = number of buckets

Bucket sort worst case

In the worst case scenario, all elements end up in the same bucket in reverse order. This may be the result of an inappropriate data distribution for this algorithm, or an incorrectly implemented variance function. In this case, the time complexity approaches O(n²).

Bucket Sort implementation, Java code

Now we will show the implementation of the bucket sort algorithm in Java.

BucketSort.java

package sorting;

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
    public void sort(float[] data)
    {
        // Set optimal bucket count here
        int bucketCount = 10;
        ArrayList<Float>[] buckets = new ArrayList[bucketCount];

        // Create empty buckets
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // Scatter elements into buckets using appropriate hash function
        for (float f : data) {
            int bucketIndex = (int) Math.floor(f * 10);
            buckets[bucketIndex].add(f);
        }

        System.out.println("After distribution:");
        for (int i = 0; i < bucketCount; i++) {
            printBucket(i, buckets[i]);
        }

        // Sort all the buckets
        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(buckets[i]);
        }

        System.out.println("After sorting individual buckets:");
        for (int i = 0; i < bucketCount; i++) {
            printBucket(i, buckets[i]);
        }

        // Concatenate buckets elements to get sorted data
        int j = 0;
        for (int i = 0; i < bucketCount; i++) {
            for (float num : buckets[i]) {
                data[j++] = num;
            }
        }
    }

    public void printBucket(int id, ArrayList<Float> data)
    {
        System.out.println("Bucket " + id + " -> " + data);
    }

    // Function to print an array
    public void printArray(float[] data)
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
    }
}

Main.java

import sorting.BucketSort;

public class Main {
    public static void main(String[] args) {
        float[] dataToSort = { 0.88f, 0.16f, 0.39f, 0.26f, 0.82f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f };
        BucketSort bucketSort = new BucketSort();
        System.out.print("Input: ");
        bucketSort.printArray(dataToSort);
        System.out.println();
        bucketSort.sort(dataToSort);
        System.out.print("Sorted: ");
        bucketSort.printArray(dataToSort);
    }
}

The output of this bucket sort Java example is:

We have prepared the files with the above example as code that you can run directly in Java. Download the Java BucketSort code.

If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers!

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.