public class CountingSort {

    /**
     * Sorts an integer array using Counting Sort.
     * Assumes all values are non-negative integers.
     */
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;

        // Step 1: Find the maximum value to determine the count array size
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }

        // Step 2: Build the count array
        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }

        // Step 3: Reconstruct the sorted array
        int index = 0;
        for (int value = 0; value <= max; value++) {
            while (count[value] > 0) {
                arr[index] = value;
                index++;
                count[value]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {4, 2, 7, 1, 4, 2, 3};
        countingSort(data);
        // Output: [1, 2, 2, 3, 4, 4, 7]
        for (int num : data) System.out.print(num + " ");
    }
}

public class RadixSort {

    /**
     * Sorts an array of non-negative integers using Radix Sort (LSD).
     * Uses Counting Sort as the stable sub-routine for each digit.
     */
    public static void radixSort(int[] arr) {
        if (arr.length == 0) return;

        // Find the maximum number to determine how many digit passes we need
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }

        // Process each digit: exp = 1 (ones), 10 (tens), 100 (hundreds), ...
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    /**
     * Counting Sort on a specific digit position determined by exp.
     * For exp=1, sorts by ones digit; exp=10, sorts by tens; etc.
     */
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // digits 0–9

        // Count occurrences of each digit
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // Convert counts to cumulative positions (for stability)
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array (process RIGHT to LEFT to maintain stability)
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy the output back into the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] data = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(data);
        // Output: [2, 24, 45, 66, 75, 90, 170, 802]
        for (int num : data) System.out.print(num + " ");
    }
}

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

public class BucketSort {

    /**
     * Sorts an array of floats in [0, 1) using Bucket Sort.
     */
    public static void bucketSort(float[] arr) {
        int n = arr.length;
        if (n <= 0) return;

        // Create n empty buckets
        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // Distribute elements into buckets
        for (float value : arr) {
            int bucketIndex = (int) (value * n); // maps [0,1) to bucket indices
            buckets[bucketIndex].add(value);
        }

        // Sort each bucket (Insertion Sort via Collections.sort for small lists)
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // Concatenate all buckets back into the original array
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float value : bucket) {
                arr[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        float[] data = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f};
        bucketSort(data);
        // Output: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]
        for (float num : data) System.out.print(num + " ");
    }
}