// 13. hét – Rendezések összehasonlítása: O(n²) vs O(n log n)
// Futtatás: java SortBenchmark.java
import java.util.Arrays;
import java.util.Random;

public class SortBenchmark {

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

    static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
        if (hi - lo < 1) return;
        int mid = (lo + hi) >>> 1;
        mergeSort(a, tmp, lo, mid);
        mergeSort(a, tmp, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    }

    static final Random RND = new Random(1);

    static void quickSort(int[] a, int lo, int hi) {
        while (lo < hi) {
            int r = lo + RND.nextInt(hi - lo + 1);
            int t = a[r]; a[r] = a[hi]; a[hi] = t;
            int pivot = a[hi], i = lo - 1;
            for (int j = lo; j < hi; j++) if (a[j] < pivot) { i++; t = a[i]; a[i] = a[j]; a[j] = t; }
            t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
            int p = i + 1;
            // a kisebbik részre rekurzió, a nagyobbikra ciklus: a veremmélység O(log n) marad
            if (p - lo < hi - p) { quickSort(a, lo, p - 1); lo = p + 1; }
            else { quickSort(a, p + 1, hi); hi = p - 1; }
        }
    }

    public static void main(String[] args) {
        System.out.printf("%10s %12s %12s %12s %14s%n", "n", "beszúrásos", "összefésülő", "gyors", "Arrays.sort");
        for (int n : new int[] { 1_000, 10_000, 100_000, 1_000_000 }) {
            int[] base = new Random(n).ints(n, 0, Integer.MAX_VALUE).toArray();
            String ins = "–";
            if (n <= 100_000) {
                int[] a = base.clone();
                long t0 = System.nanoTime();
                insertionSort(a);
                ins = String.format("%.1f ms", (System.nanoTime() - t0) / 1e6);
            }
            int[] b = base.clone();
            long t1 = System.nanoTime();
            mergeSort(b, new int[n], 0, n - 1);
            long t2 = System.nanoTime();
            int[] c = base.clone();
            quickSort(c, 0, n - 1);
            long t3 = System.nanoTime();
            int[] d = base.clone();
            Arrays.sort(d);
            long t4 = System.nanoTime();
            if (!Arrays.equals(b, d) || !Arrays.equals(c, d)) throw new AssertionError("hibás rendezés!");
            System.out.printf("%10d %12s %9.1f ms %9.1f ms %11.1f ms%n", n, ins, (t2 - t1) / 1e6, (t3 - t2) / 1e6, (t4 - t3) / 1e6);
        }
    }
}