import java.util.Arrays;
import java.util.Random;

/** Bubble, selection and insertion sort with pass-by-pass traces, counters and a stability test. */
public class SimpleSorts {

    static long comparisons, swaps;

    // BEGIN bubble
    static void bubbleSort(int[] a) {
        int n = a.length;
        for (int pass = 1; pass < n; pass++) {
            for (int j = 0; j < n - pass; j++) {            // the last `pass` items are already in place
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                }
            }
        }
    }
    // END bubble

    // BEGIN bubbleEarly
    static int bubbleSortEarlyExit(int[] a) {
        int n = a.length, passes = 0;
        boolean swapped = true;
        for (int pass = 1; pass < n && swapped; pass++) {
            swapped = false;
            passes++;
            for (int j = 0; j < n - pass; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                    swapped = true;
                }
            }
        }
        return passes;                                       // a pass with no swap means: sorted, stop
    }
    // END bubbleEarly

    // BEGIN selection
    static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) min = j;                  // remember where the smallest remaining item is
            }
            int t = a[i]; a[i] = a[min]; a[min] = t;         // one swap per pass
        }
    }
    // END selection

    // BEGIN insertion
    static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {                   // shift larger items one place right
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;                                  // drop the key into the gap
        }
    }
    // END insertion

    // ---- instrumented copies (same logic, with counters and trace output) ----
    static void bubbleTrace(int[] a) {
        comparisons = swaps = 0;
        System.out.println("start        " + Arrays.toString(a));
        for (int pass = 1; pass < a.length; pass++) {
            int sw = 0;
            for (int j = 0; j < a.length - pass; j++) {
                comparisons++;
                if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swaps++; sw++; }
            }
            System.out.printf("pass %d (%d swaps) %s%n", pass, sw, Arrays.toString(a));
        }
    }

    static void selectionTrace(int[] a) {
        comparisons = swaps = 0;
        System.out.println("start        " + Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) { comparisons++; if (a[j] < a[min]) min = j; }
            int t = a[i]; a[i] = a[min]; a[min] = t; swaps++;
            System.out.printf("pass %d (min=%d at index %d) %s%n", i + 1, a[i], min, Arrays.toString(a));
        }
    }

    static void insertionTrace(int[] a) {
        comparisons = swaps = 0;
        System.out.println("start        " + Arrays.toString(a));
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1, shifts = 0;
            while (j >= 0) { comparisons++; if (a[j] > key) { a[j + 1] = a[j]; j--; shifts++; } else break; }
            a[j + 1] = key; swaps += shifts;
            System.out.printf("insert %d (%d shifts) %s%n", key, shifts, Arrays.toString(a));
        }
    }

    static long[] count(String which, int[] src) {
        int[] a = src.clone();
        comparisons = swaps = 0;
        switch (which) {
            case "bubble" -> {
                for (int pass = 1; pass < a.length; pass++)
                    for (int j = 0; j < a.length - pass; j++) { comparisons++; if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swaps++; } }
            }
            case "bubble+exit" -> {
                boolean sw = true;
                for (int pass = 1; pass < a.length && sw; pass++) { sw = false;
                    for (int j = 0; j < a.length - pass; j++) { comparisons++; if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swaps++; sw = true; } } }
            }
            case "selection" -> {
                for (int i = 0; i < a.length - 1; i++) { int min = i;
                    for (int j = i + 1; j < a.length; j++) { comparisons++; if (a[j] < a[min]) min = j; }
                    if (min != i) { int t = a[i]; a[i] = a[min]; a[min] = t; swaps++; } }
            }
            default -> {
                for (int i = 1; i < a.length; i++) { int key = a[i], j = i - 1;
                    while (j >= 0) { comparisons++; if (a[j] > key) { a[j + 1] = a[j]; j--; swaps++; } else break; }
                    a[j + 1] = key; }
            }
        }
        return new long[]{comparisons, swaps};
    }

    record Item(String name, int marks) {}

    // BEGIN stability
    static void selectionSortItems(Item[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (a[j].marks() < a[min].marks()) min = j;
            Item t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }

    static void insertionSortItems(Item[] a) {
        for (int i = 1; i < a.length; i++) {
            Item key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j].marks() > key.marks()) { a[j + 1] = a[j]; j--; }
            a[j + 1] = key;
        }
    }
    // END stability

    public static void main(String[] args) {
        System.out.println("=== Bubble sort trace ===");
        bubbleTrace(new int[]{5, 1, 4, 2, 8});
        System.out.println("comparisons=" + comparisons + " swaps=" + swaps);

        System.out.println();
        System.out.println("=== Selection sort trace ===");
        selectionTrace(new int[]{5, 1, 4, 2, 8});
        System.out.println("comparisons=" + comparisons + " swaps=" + swaps);

        System.out.println();
        System.out.println("=== Insertion sort trace ===");
        insertionTrace(new int[]{5, 1, 4, 2, 8});
        System.out.println("comparisons=" + comparisons + " shifts=" + swaps);

        System.out.println();
        System.out.println("=== Early exit: passes needed ===");
        System.out.println("already sorted [1, 2, 3, 4, 5, 6, 7, 8]: " + bubbleSortEarlyExit(new int[]{1, 2, 3, 4, 5, 6, 7, 8}) + " pass (plain bubble sort always makes 7)");
        System.out.println("one swap away  [1, 2, 4, 3, 5, 6, 7, 8]: " + bubbleSortEarlyExit(new int[]{1, 2, 4, 3, 5, 6, 7, 8}) + " passes");
        System.out.println("reversed       [8, 7, 6, 5, 4, 3, 2, 1]: " + bubbleSortEarlyExit(new int[]{8, 7, 6, 5, 4, 3, 2, 1}) + " passes");

        System.out.println();
        System.out.println("=== Counted operations, n = 1000 ===");
        int n = 1000;
        int[] sorted = new int[n], reversed = new int[n], random = new int[n];
        Random r = new Random(42);
        for (int i = 0; i < n; i++) { sorted[i] = i; reversed[i] = n - i; random[i] = r.nextInt(100_000); }
        System.out.printf("%-12s %-10s %12s %12s%n", "algorithm", "input", "comparisons", "swaps/shifts");
        for (String alg : new String[]{"bubble", "bubble+exit", "selection", "insertion"}) {
            for (Object[] in : new Object[][]{{"sorted", sorted}, {"random", random}, {"reversed", reversed}}) {
                long[] c = count(alg, (int[]) in[1]);
                System.out.printf("%-12s %-10s %12d %12d%n", alg, in[0], c[0], c[1]);
            }
        }

        System.out.println();
        System.out.println("=== Stability: sort by marks, equal marks must keep input order ===");
        Item[] a = {new Item("Asha", 80), new Item("Bala", 80), new Item("Chitra", 60)};
        System.out.println("input     : " + Arrays.toString(a));
        Item[] s = a.clone(); selectionSortItems(s);
        System.out.println("selection : " + Arrays.toString(s));
        Item[] ins = a.clone(); insertionSortItems(ins);
        System.out.println("insertion : " + Arrays.toString(ins));

        System.out.println();
        int[] check = random.clone(); bubbleSort(check);
        int[] c2 = random.clone(); selectionSort(c2);
        int[] c3 = random.clone(); insertionSort(c3);
        int[] ref = random.clone(); Arrays.sort(ref);
        System.out.println("All three match Arrays.sort on 1000 random values: "
                + (Arrays.equals(check, ref) && Arrays.equals(c2, ref) && Arrays.equals(c3, ref)));
    }
}