Bucket Sort in Java

In the bucket sort algorithm, we will create multiple small groups containing a range of elements (called buckets). Then these groups are back joined again and the sorted array is formed. This method is also known as the “scatter and gather algorithm“.

Bucket Sort Procedure:

Basic Ideology behind bucket sort is:

1. Partition the range into number of buckets.
2. Put each element into its corresponding bucket.
3. Sort each bucket individually by applying a sorting algorithm(most probably insertion sort).
4. Merge all sorted buckets to get the sorted array.

Bucket Sort Algorithm:

bucket_sort(a[],n)
    Create buckets
    Initializing all buckets to zero i.e  Empty buckets
    For each element in array[]:
         Add them to their corresponding bucket.
    Sort all buckets individually using any sorting algorithm.
    Merge the sorted buckets together.

Bucket Sort Example:

How do you sort a bucket?

Suppose, let an array to be sorted is [4 8 2 12 16 19 13 6 7 11] and no of buckets be 4.

   Let range of bucket 1 be: 0-5
   Let range of bucket 2 be: 5-10
   Let range of bucket 3 be: 10-15
   Let range of bucket 4 be: 15-20

After traversing the whole array, buckets will be as follows:

   Bucket 1 :   [4,2]
   Bucket 2 :   [8,6,7]
   Bucket 3 :   [12,13,11]
   Bucket 4 :   [16,19]

Sorting each bucket with any of the sorting algorithm (Insertion sort most probably), so buckets are as follows:

   Bucket 1 :   [2,4]
   Bucket 2 :   [6,7,8]
   Bucket 3 :   [11,12,13]
   Bucket 4 :   [16,19]

Now Merging the buckets together:

Sorted Array : [2,4,6,7,8,11,12,13,16,19]

In this program, we sort the numbers using the Bucket Sort technique. The algorithm allocates a number of memory locations equal to maximum number and initializes all to zero, then each location is incremented as the numbers appears. The time complexity of the algorithm is O(n).

Here is the source code of the Java Program to Implement Bucket Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to sort numbers using bucket sort
 
import java.util.Random;
 
public class Bucket_Sort 
{
    static int[] sort(int[] sequence, int maxValue) 
    {
        // Bucket Sort
        int[] Bucket = new int[maxValue + 1];
        int[] sorted_sequence = new int[sequence.length];
 
        for (int i = 0; i < sequence.length; i++)
            Bucket[sequence[i]]++;
 
        int outPos = 0;
        for (int i = 0; i < Bucket.length; i++)
            for (int j = 0; j < Bucket[i]; j++)
                sorted_sequence[outPos++] = i;
 
        return sorted_sequence;
    }
 
    static void printSequence(int[] sorted_sequence) 
    {
        for (int i = 0; i < sorted_sequence.length; i++)
            System.out.print(sorted_sequence[i] + " ");
    }
 
    static int maxValue(int[] sequence) 
    {
        int maxValue = 0;
        for (int i = 0; i < sequence.length; i++)
            if (sequence[i] > maxValue)
                maxValue = sequence[i];
        return maxValue;
    }
 
    public static void main(String args[]) 
    {
        System.out
                .println("Sorting of randomly generated numbers using BUCKET SORT");
        Random random = new Random();
        int N = 20;
        int[] sequence = new int[N];
 
        for (int i = 0; i < N; i++)
            sequence[i] = Math.abs(random.nextInt(100));
 
        int maxValue = maxValue(sequence);
 
        System.out.println("\nOriginal Sequence: ");
        printSequence(sequence);
 
        System.out.println("\nSorted Sequence: ");
        printSequence(sort(sequence, maxValue));
    }
}

1. The user defines the length of the sequence, and the program generates an array of random integers between 0 and 100.
2. Find the maximum value in the sequence.
3. Create a bucket array of size maxValue+1 and initialize all elements to 0.
4. Increment the value of the corresponding bucket for each element in the sequence.
5. Create a sorted_sequence array and add the corresponding index value to the array based on the count of the corresponding bucket.
6. Print out the original and sorted sequences.

Time Complexity: O(n+k)
The time complexity of the Bucket Sort algorithm used in this program is O(n+k), where n is the number of elements in the input sequence, and k is the range of the values in the sequence.

Space Complexity: O(n+k)
The space complexity is O(n+k), as the algorithm requires additional space to store the buckets and the sorted sequence. The main function generates a sequence of 20 random integers between 0 and 100, and then sorts it using Bucket Sort.

 
$ javac Bucket_Sort.java
$ java Bucket_Sort
 
Sorting of randomly generated numbers using BUCKET SORT
 
Original Sequence: 
95 9 95 87 8 81 18 54 57 53 92 15 38 24 8 56 29 69 64 66 
Sorted Sequence: 
8 8 9 15 18 24 29 38 53 54 56 57 64 66 69 81 87 92 95 95

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.