1. Introduction

Bucket Sort is a sorting algorithm that divides the input array into k equally-sized “buckets”. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying the bucket sort. Once all the buckets are sorted, the values are concatenated to get the sorted array. Bucket sort is mainly useful when the input is uniformly distributed over a range.

2. Program Steps

1. Determine the maximum and minimum values in the input and use them to determine the range and size of the buckets.

2. Create an array of empty buckets.

3. Scatter: Go over the original array, putting each object in its bucket.

4. For each bucket, sort its elements.

5. Gather: Concatenate the elements of the buckets to get the sorted array.

3. Code Program

import java.util.*;

public class BucketSort {

    // Function to sort arr[] using bucket sort
    static void bucketSort(float arr[], int n) {
        // 1. Create n empty buckets
        ArrayList<Float>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<Float>();
        }

        // 2. Put array elements in different buckets
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n);
            buckets[bucketIndex].add(arr[i]);
        }

        // 3. Sort individual buckets
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]);
        }

        // 4. Concatenate all buckets into arr[]
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                arr[index++] = buckets[i].get(j);
            }
        }
    }

    // Driver code
    public static void main(String args[]) {
        float arr[] = {(float) 0.897, (float) 0.565, (float) 0.656, (float) 0.1234, (float) 0.665, (float) 0.3434};
        int n = arr.length;

        bucketSort(arr, n);

        System.out.println("Sorted array:");
        for (float el : arr) {
            System.out.print(el + " ");
        }
    }
}

Output:

Sorted array:
0.1234 0.3434 0.565 0.656 0.665 0.897

4. Step By Step Explanation

1. bucketSort function: This function first creates n empty buckets represented as ArrayLists.

2. Each element in the array arr is then assigned to a bucket. The bucket in which an element goes is determined by multiplying the element by n and taking the integer value. This method ensures that elements are distributed uniformly across the buckets.

3. Once the elements are placed in the buckets, each bucket is sorted using the Collections.sort() function. Note that any sorting algorithm can be used to sort the buckets.

4. After sorting each bucket, the buckets are concatenated to get the final sorted array.

It's important to understand that Bucket Sort works well when the input elements are uniformly distributed over a range. Otherwise, most of the elements might get concentrated in a few buckets, not leveraging the advantage of this algorithm.