// Week 5 – Comparing the simple sorts: comparisons, moves, time
// Run: java SortCompare.java
import java.util.Random;

public class SortCompare {
    static long cmp, mov; // number of comparisons and of element moves (assignments)

    static boolean less(int x, int y) { cmp++; return x < y; }

    static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
        mov += 3;
    }

    static void bubble(int[] a) {
        for (int i = a.length - 1; i >= 1; i--) {
            boolean swapped = false;
            for (int j = 0; j < i; j++) {
                if (less(a[j + 1], a[j])) { swap(a, j, j + 1); swapped = true; }
            }
            if (!swapped) break;
        }
    }

    static void selection(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (less(a[j], a[min])) min = j;
            swap(a, i, min);
        }
    }

    static void insertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int x = a[i]; mov++;
            int j = i - 1;
            while (j >= 0 && less(x, a[j])) { a[j + 1] = a[j]; mov++; j--; }
            a[j + 1] = x; mov++;
        }
    }

    static int[] make(String kind, int n, Random rnd) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            switch (kind) {
                case "sorted" -> a[i] = i;
                case "reversed" -> a[i] = n - i;
                default -> a[i] = rnd.nextInt(n);
            }
        }
        return a;
    }

    interface Sorter { void sort(int[] a); }

    public static void main(String[] args) {
        Random rnd = new Random(42);
        String[] names = { "bubble", "selection", "insertion" };
        Sorter[] sorters = { SortCompare::bubble, SortCompare::selection, SortCompare::insertion };

        int n = 1000;
        System.out.println("n = " + n + ": comparisons / moves");
        System.out.printf("%-14s %22s %22s %22s%n", "", "random", "sorted", "reversed");
        for (int s = 0; s < 3; s++) {
            System.out.printf("%-14s", names[s]);
            for (String kind : new String[] { "random", "sorted", "reversed" }) {
                int[] a = make(kind, n, rnd);
                cmp = mov = 0;
                sorters[s].sort(a);
                System.out.printf(" %10d / %9d", cmp, mov);
            }
            System.out.println();
        }

        System.out.println("\nTime on random data (ms) – roughly four times as much when n doubles:");
        System.out.printf("%8s %12s %12s %12s%n", "n", "bubble", "selection", "insertion");
        for (n = 2000; n <= 16000; n *= 2) {
            System.out.printf("%8d", n);
            int[] base = make("random", n, rnd);
            for (Sorter srt : sorters) {
                int[] a = base.clone();
                long t0 = System.nanoTime();
                srt.sort(a);
                System.out.printf(" %12.1f", (System.nanoTime() - t0) / 1e6);
            }
            System.out.println();
        }
    }
}