How to implement Bucket Sort Algorithm in Java? Detailed Explanation

Bucket sort is a sorting algorithm used to sort a collection of floating-point numbers into increasing order.

The algorithm works by dividing the range of the input numbers into n buckets, where n is the number of elements in the input array. Each bucket is represented as a list, and the input numbers are then distributed into the buckets based on their value.

Once the input numbers are distributed into the buckets, each bucket is sorted using a separate sorting algorithm, such as insertion sort or quicksort. The sorted buckets are then combined to produce the final sorted array.

Bucket sort has a time complexity of O(n), making it an efficient sorting algorithm for collections of numbers that are uniformly distributed in a range. However, it is not suitable for sorting collections of numbers that are not uniformly distributed, as it can result in unbalanced bucket sizes and slow performance.

CrunchifyBucketSortAlgorithm.java

package crunchify.com.java.tutorials;

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

/**
 * @author Crunchify.com
 * Program: How to implement Bucket Sort Algorithm in Java??
 * Bucket sort is a sorting algorithm used to sort a collection of floating-point numbers into increasing order...
 */


public class CrunchifyBucketSortAlgorithm {


    public static void main(String[] args) {
        float[] crunchifyArray = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
        
        crunchifyBucketSort(crunchifyArray);
        crunchifyPrint("\n Here is a Final Sorted array:");
        
        for (float crunchifyItem : crunchifyArray) {
            crunchifyPrint("  " + crunchifyItem + " ");
        }
    }

    private static void crunchifyPrint(String crunchify) {

        System.out.println(crunchify);
    }
    public static void crunchifyBucketSort(float[] crunchifyArray) {
        int totalCount = crunchifyArray.length;
        ArrayList<Float>[] crunchifyBuckets = new ArrayList[totalCount];

        for (int i = 0; i < totalCount; i++) {
            crunchifyBuckets[i] = new ArrayList<Float>();
        }

        System.out.println("\n Distributing numbers into buckets:");
        for (float crunchifyItem : crunchifyArray) {
            int index = (int) (totalCount * crunchifyItem);
            crunchifyPrint("  " + crunchifyItem + " -> bucket " + index);
            crunchifyBuckets[index].add(crunchifyItem);
        }

        System.out.println("\n Sorting individual buckets:");
        for (ArrayList<Float> myBucket : crunchifyBuckets) {
            Collections.sort(myBucket);
            crunchifyPrint("  " + myBucket);
        }

        System.out.println("\n Merging sorted buckets:");
        int index = 0;
        for (ArrayList<Float> myBucket : crunchifyBuckets) {
            for (float crunchifyItem : myBucket) {
                crunchifyArray[index++] = crunchifyItem;
                crunchifyPrint("  " + crunchifyItem);
            }
        }
    }

}

Explanation of Bucket Sort Algorithm

The program above implements the bucket sort algorithm in Java. Bucket sort is an algorithm used for sorting a collection of floating-point numbers, usually between 0 and 1, into increasing order.

The program defines a sort method that takes an array of floating-point numbers as an argument. Here’s a step-by-step explanation of the algorithm:

1. Create an array of n buckets, where n is the number of elements in the input array. Each bucket is represented as an ArrayList of floating-point numbers.
2. Distribute the numbers in the input array into the buckets. This is done by calculating the index of the bucket for each number, which is (int) (n * item), where item is the number being distributed. The number is then added to the ArrayList for that index.
3. Sort each bucket using the Collections.sort method.
4. Merge the sorted buckets back into the original array in the correct order. This is done by iterating through the buckets, and for each bucket, iterating through its contents and adding the numbers back into the original array in the order they appear.

The program also contains additional logging statements to show the distribution of numbers into buckets, the sorting of individual buckets, and the merging of sorted buckets back into the original array.

Finally, the main method creates a test array of floating-point numbers and sorts it using the sort method, printing the sorted array to the console.

Just run above program has a Java Application and you will see result as below.

IntelliJ IDEA Console Result

 Distributing numbers into buckets:
  0.897 -> bucket 5
  0.565 -> bucket 3
  0.656 -> bucket 3
  0.1234 -> bucket 0
  0.665 -> bucket 3
  0.3434 -> bucket 2

 Sorting individual buckets:
  [0.1234]
  []
  [0.3434]
  [0.565, 0.656, 0.665]
  []
  [0.897]

 Merging sorted buckets:
  0.1234
  0.3434
  0.565
  0.656
  0.665
  0.897

 Here is a Final Sorted array:
  0.1234 
  0.3434 
  0.565 
  0.656 
  0.665 
  0.897 

Process finished with exit code 0

Let me know if you face any issue running above Java program.

The post How to implement Bucket Sort Algorithm in Java? Detailed Explanation appeared first on Crunchify.