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

/** Independent teaching implementation. Java 8+, no external dependencies. */
public final class SortingLab {
    private final int[] a;
    private final int[] ids;
    private final boolean trace;
    private long comparisons;
    private long writes;

    public SortingLab(int[] input, boolean trace) {
        this.a = input.clone();
        this.ids = new int[input.length];
        this.trace = trace;
        for (int i = 0; i < ids.length; i++) ids[i] = i;
    }

    private int compare(int x, int y) {
        comparisons++;
        return Integer.compare(x, y);
    }

    private void put(int index, int value, int id) {
        a[index] = value;
        ids[index] = id;
        writes++; // Count writes to the data array, not metadata or local variables.
    }

    private void swap(int i, int j) {
        if (i == j) return;
        int value = a[i], id = ids[i];
        put(i, a[j], ids[j]);
        put(j, value, id);
    }

    public void selectionSort() {
        for (int i = 0; i + 1 < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (compare(a[j], a[min]) < 0) min = j;
                frame("Find the smallest remaining card", j, min, i, -1, 0, -1);
            }
            swap(i, min);
            frame("One more card is in its final position", i, min, i + 1, -1, 0, -1);
        }
    }

    public void insertionSort() {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], keyId = ids[i];
            int j = i - 1;
            frame("Lift one card; keep it in hand", i, j, i, i, key, keyId);
            while (j >= 0) {
                if (compare(a[j], key) <= 0) break;
                put(j + 1, a[j], ids[j]);
                frame("Shift a larger card into the empty slot", j + 1, j, i, j, key, keyId);
                j--;
            }
            put(j + 1, key, keyId);
            frame("The prefix is ordered, not fixed forever", j + 1, i, i + 1, -1, 0, -1);
        }
    }

    public void bubbleSort() {
        for (int end = a.length - 1; end > 0; end--) {
            boolean changed = false;
            for (int j = 0; j < end; j++) {
                if (compare(a[j], a[j + 1]) > 0) {
                    swap(j, j + 1);
                    changed = true;
                }
                frame("Compare neighbours; the maximum moves right", j, j + 1, end, -1, 0, -1);
            }
            frame("The rightmost active card is now fixed", end, -1, end, -1, 0, -1);
            if (!changed) break;
        }
    }

    public void quickSort() {
        quickSort(0, a.length - 1);
    }

    private void quickSort(int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(lo, hi);
        quickSort(lo, p - 1);
        quickSort(p + 1, hi);
    }

    private int partition(int lo, int hi) {
        int pivot = a[hi];
        int boundary = lo;
        frame("Partition: pivot is the last card of this range", lo, hi, boundary, -1, 0, -1);
        for (int scan = lo; scan < hi; scan++) {
            if (compare(a[scan], pivot) < 0) {
                swap(boundary, scan);
                boundary++;
            }
            frame("Left of boundary < pivot; scanned right >= pivot", scan, hi, boundary, -1, 0, -1);
        }
        swap(boundary, hi);
        frame("Pivot is fixed; the two sides still need sorting", boundary, hi, boundary, -1, 0, -1);
        return boundary;
    }

    public void sort(String name) {
        frame("Start with the same six cards", -1, -1, 0, -1, 0, -1);
        switch (name) {
            case "selection": selectionSort(); break;
            case "insertion": insertionSort(); break;
            case "bubble": bubbleSort(); break;
            case "quick": quickSort(); break;
            default: throw new IllegalArgumentException("Unknown algorithm: " + name);
        }
        frame("Sorted by key; check equal-key identities too", -1, -1, a.length, -1, 0, -1);
    }

    private void frame(String text, int first, int second, int boundary,
                       int hole, int heldValue, int heldId) {
        if (!trace) return;
        System.out.println("{\"values\":" + Arrays.toString(a)
            + ",\"ids\":" + Arrays.toString(ids)
            + ",\"text\":\"" + text + "\",\"first\":" + first
            + ",\"second\":" + second + ",\"boundary\":" + boundary
            + ",\"hole\":" + hole + ",\"heldValue\":" + heldValue
            + ",\"heldId\":" + heldId + ",\"comparisons\":" + comparisons
            + ",\"writes\":" + writes + "}");
    }

    private static void require(boolean ok, String message) {
        if (!ok) throw new AssertionError(message);
    }

    private static void check(int[] input, String name) {
        int[] expected = input.clone();
        Arrays.sort(expected);
        int[] plain = input.clone();
        switch (name) {
            case "selection": Sorting.selectionSort(plain); break;
            case "insertion": Sorting.insertionSort(plain); break;
            case "bubble": Sorting.bubbleSort(plain); break;
            case "quick": Sorting.quickSort(plain); break;
            default: throw new IllegalArgumentException(name);
        }
        require(Arrays.equals(expected, plain), name + " plain implementation output");
        SortingLab lab = new SortingLab(input, false);
        lab.sort(name);
        require(Arrays.equals(expected, lab.a), name + " output");
        boolean[] seen = new boolean[input.length];
        for (int i = 0; i < input.length; i++) {
            require(!seen[lab.ids[i]], name + " duplicated identity");
            seen[lab.ids[i]] = true;
            require(lab.a[i] == input[lab.ids[i]], name + " changed a record");
            if (i > 0 && lab.a[i] == lab.a[i - 1]
                    && (name.equals("insertion") || name.equals("bubble"))) {
                require(lab.ids[i - 1] < lab.ids[i], name + " lost stability");
            }
        }
    }

    private static void test() {
        String[] names = {"selection", "insertion", "bubble", "quick"};
        int cases = 0;
        for (int n = 0, count = 1; n <= 7; n++, count *= 3) {
            for (int encoded = 0; encoded < count; encoded++) {
                int[] values = new int[n];
                for (int j = 0, v = encoded; j < n; j++, v /= 3) values[j] = v % 3 - 1;
                for (String name : names) { check(values, name); cases++; }
            }
        }
        Random random = new Random(20261008L);
        for (int trial = 0; trial < 500; trial++) {
            int[] values = new int[random.nextInt(80)];
            for (int i = 0; i < values.length; i++) values[i] = random.nextInt();
            for (String name : names) { check(values, name); cases++; }
        }
        for (String name : names) {
            check(new int[]{Integer.MAX_VALUE, 0, Integer.MIN_VALUE, -1, 0}, name); cases++;
        }
        for (int n = 0; n < 65; n++) {
            int[] sorted = new int[n], reverse = new int[n];
            for (int i = 0; i < n; i++) { sorted[i] = i; reverse[i] = n - i; }
            long pairs = (long) n * (n - 1) / 2;
            for (String name : names) {
                SortingLab lab = new SortingLab(sorted, false); lab.sort(name);
                require(lab.comparisons == (name.equals("selection") || name.equals("quick")
                    ? pairs : Math.max(0, n - 1)), name + " sorted count");
            }
            SortingLab insertion = new SortingLab(reverse, false); insertion.insertionSort();
            require(insertion.comparisons == pairs, "insertion reverse count");
        }
        SortingLab witness = new SortingLab(new int[]{2, 2, 1}, false);
        witness.selectionSort();
        require(Arrays.equals(witness.ids, new int[]{2, 1, 0}), "selection instability witness");
        System.out.println("PASS: " + cases + " sort cases; permutation and stable variants checked.");
        System.out.println("PASS: exact count formulas n=0..64; selection instability witness.");
    }

    private static void metrics() {
        String[] names = {"selection", "insertion", "bubble", "quick"};
        int[][] inputs = {{7,3,5,3,9,1}, {1,2,3,4,5,6}, {6,5,4,3,2,1}, {3,3,3,3,3,3}};
        String[] labels = {"six-cards", "sorted", "reverse", "equal"};
        System.out.println("dataset,algorithm,key_comparisons,array_writes");
        for (int i = 0; i < inputs.length; i++) {
            for (String name : names) {
                SortingLab lab = new SortingLab(inputs[i], false); lab.sort(name);
                System.out.println(labels[i] + "," + name + "," + lab.comparisons + "," + lab.writes);
            }
        }
    }

    public static void main(String[] args) {
        if (args.length == 0 || args[0].equals("test")) { test(); return; }
        if (args[0].equals("metrics")) { metrics(); return; }
        if (args.length < 2 || !args[0].equals("trace")) {
            throw new IllegalArgumentException("test | metrics | trace ALGORITHM [integers...]");
        }
        int[] values = {7,3,5,3,9,1};
        if (args.length > 2) {
            values = new int[args.length - 2];
            for (int i = 0; i < values.length; i++) values[i] = Integer.parseInt(args[i + 2]);
        }
        new SortingLab(values, true).sort(args[1]);
    }
}