// 13. hét – Gyorsrendezés (quicksort) Lomuto-particionálással
// Futtatás: java QuickSort.java
import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    static long comparisons = 0;
    static final Random RND = new Random(7);

    //   Eljárás Gyorsrendezés(A, bal, jobb)
    //     Ha bal < jobb akkor
    //       p ← Particionál(A, bal, jobb)
    //       Gyorsrendezés(A, bal, p − 1)
    //       Gyorsrendezés(A, p + 1, jobb)
    //   Eljárás vége
    static void quickSort(int[] a, int lo, int hi, boolean randomPivot) {
        if (lo >= hi) return;
        if (randomPivot) swap(a, lo + RND.nextInt(hi - lo + 1), hi); // véletlen pivot a végére
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1, randomPivot);
        quickSort(a, p + 1, hi, randomPivot);
    }

    // Lomuto-particionálás: pivot = a[hi]. A végén a pivot a végleges helyén van,
    // tőle balra a kisebbek, jobbra a nagyobbak vagy egyenlők. Visszaadja a pivot indexét.
    static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo - 1; // a "kisebbek" rész utolsó eleme
        for (int j = lo; j < hi; j++) {
            comparisons++;
            if (a[j] < pivot) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, hi);
        return i + 1;
    }

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

    public static void main(String[] args) {
        int[] a = { 7, 2, 9, 4, 3, 8, 6 };
        int[] b = a.clone();
        int p = partition(b, 0, b.length - 1);
        System.out.println("partition([7,2,9,4,3,8,6]) -> " + Arrays.toString(b) + ", pivot indexe: " + p);
        quickSort(a, 0, a.length - 1, false);
        System.out.println("quickSort -> " + Arrays.toString(a));

        // Legrosszabb eset: már rendezett tömb, utolsó elem pivotként → O(n²)
        int n = 5000;
        int[] sorted = new int[n];
        for (int i = 0; i < n; i++) sorted[i] = i;
        comparisons = 0;
        quickSort(sorted.clone(), 0, n - 1, false);
        System.out.printf("%nrendezett bemenet, n = %d, fix pivot:     %,12d összehasonlítás (≈ n²/2 = %,d)%n", n, comparisons, (long) n * n / 2);
        comparisons = 0;
        quickSort(sorted.clone(), 0, n - 1, true);
        System.out.printf("rendezett bemenet, n = %d, véletlen pivot: %,12d összehasonlítás (≈ 1,39·n·log₂n = %,d)%n", n, comparisons,
                (long) (1.39 * n * Math.log(n) / Math.log(2)));
    }
}