Bucket Sort Algorithm in Java

1. Introduction

Bucket Sort is a non-comparative sorting algorithm that distributes elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying bucket sort. Bucket sort is mainly useful when input is uniformly distributed over a range.

2. Implementation Steps

1. Create an array of lists (buckets).

2. For each element in the original array, determine which bucket it belongs to and add it to that bucket.

3. Sort each bucket.

4. Concatenate all buckets to get the sorted array.

3. Implementation in Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void sort(float[] arr) {
        int n = arr.length;
        // 1. Create empty buckets
        List<Float>[] buckets = new List[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 2. Add elements into the buckets
        for (float num : arr) {
            int bucketIndex = (int) (num * n);
            buckets[bucketIndex].add(num);
        }
        // 3. Sort each bucket
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }
        // 4. Concatenate buckets to get the sorted array
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float num : bucket) {
                arr[index++] = num;
            }
        }
    }
    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};
        System.out.println("Original array:");
        for (float i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        sort(arr);
        System.out.println("Sorted array:");
        for (float i : arr) {
            System.out.print(i + " ");
        }
    }
}

Output:

Original array:
0.42 0.32 0.33 0.52 0.37 0.47 0.51
Sorted array:
0.32 0.33 0.37 0.42 0.47 0.51 0.52

Explanation:

1. Begin by creating an array of lists, which will act as buckets.

2. For every element in the input array, determine its appropriate bucket and place it inside. This is typically done using the element's value as an index.

3. Once all elements are placed in their respective buckets, each bucket is sorted. This can be done using any sorting method; in this example, we've used the Java Collections.sort() method.

4. Finally, concatenate all the buckets in order to produce the sorted array.