Class Main

Lecture 43 Non-Comparison Sorting/src/Main.java:3–117

import java.util.*;

public class Main {
    public static void bbucketSort(float[] arr) {
        //Let's create 10 buckets
        ArrayList<ArrayList<Float>> buckets = new ArrayList<>();
        // Initialize each bucket
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        // Dividing arr into buckets
        for (int i = 0; i < arr.length; i++) {
            int index;
            if (arr[i] >= 1) {
                index = ((int) arr[i]) % 10;
            } else {
                index = (int) (arr[i] * 10);
            }
            buckets.get(index).add(arr[i]);
        }
        // Sorting each bucket
        for (int i = 0; i < 10; i++) {
            Collections.sort(buckets.get(i));
        }
        // Merging buckets together
        int index = 0;
        for (int bucket = 0; bucket < 10; bucket++) {
            ArrayList<Float> currBucket = buckets.get(bucket);
            for (int i = 0; i < currBucket.size(); i++) {
                arr[index++] = currBucket.get(i);
            }
        }
    }
    static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        return max;
    }
    static void countSort(int[] arr, int place) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        for (int i = 0; i < n; i++) { // Store the count of each element
            count[(arr[i] / place) % 10]++;
        }
        for (int i = 1; i < count.length; i++) { // prefix sum
            count[i] += count[i - 1];
        }
        // Find the index of each element of the original arr in count arr, and place the elements in output arr
        for (int i = n - 1; i >= 0; i--) {
            int idx = count[(arr[i] / place) % 10] - 1;
            output[idx] = arr[i];
            count[(arr[i] / place) % 10]--;
        }
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }