Bucket sort algorithm Java

Selection sort 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 a number of different sorting algorithms. 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 requirements.

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:

• Sorting algorithms: an introduction to data sorting,
• Bubble sort,
• Comb sort,
• Big O notation: analyzing the complexity of algorithms,
• Selection sort – sorting by selection,
• Insertion sort – sorting by insertion,
• Counting sort – sorting by counting,
• Heap sort,
• Merge sort – sorting by splitting and merging,
• Quick sort – fast sorting with pivot.

What is bucket sort algorithm? – 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 (see also 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 that sorts the data in each group, the number of groups, as well as the uniform distribution of the values in the input.

Bucket sort principle explained

If we need to sort a large amount of data that has the property that it is evenly sorted (e.g. order numbers), by dividing it into subgroups we can reduce the amount of inter-element comparisons, which will help us reduce sorting time. Once the data is sorted, we can keep them sorted in groups and when adding new elements to the groups, sort only the groups to which the new element was added. Sorted data is also easier and faster to sort if we use a suitable algorithm for this, such as Insertion sort. Partitioning into multiple groups will also allow us to deploy parallel sorting and data processing techniques. The basic principle of the Bucket sort algorithm is as follows:

1. Determining the quantity of buckets By passing through the values once, we can determine the maximum value
2. Creating an array of initial empty buckets
3. Distributing the elements into the corresponding buckets
   The most appropriate way to distribute the elements (scatter) using a simple hash function.
4. Sorting the elements of each bucket
5. Collect(gather) the results from each bucket in the correct order

Bucket sort animation, visualization,gif

Bucket sort algorithm 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 algorithm disadvantages

• Requires additional memory space to create groups.
• 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 example is:

We have prepared the files with the above example in the form of 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.