// Week 13 – Quicksort with Lomuto partitioning
// Run: 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);

    //   Procedure QuickSort(A, left, right)
    //     If left < right then
    //       p ← Partition(A, left, right)
    //       QuickSort(A, left, p − 1)
    //       QuickSort(A, p + 1, right)
    //   End procedure
    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); // random pivot to the end
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1, randomPivot);
        quickSort(a, p + 1, hi, randomPivot);
    }

    // Lomuto partitioning: pivot = a[hi]. At the end the pivot is in its final position,
    // smaller ones to its left, larger or equal ones to its right. Returns the index of the pivot.
    static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo - 1; // the last element of the "smaller" part
        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 index: " + p);
        quickSort(a, 0, a.length - 1, false);
        System.out.println("quickSort -> " + Arrays.toString(a));

        // Worst case: an already sorted array, the last element as pivot → 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("%nsorted input, n = %d, fixed pivot:  %,12d comparisons (≈ n²/2 = %,d)%n", n, comparisons, (long) n * n / 2);
        comparisons = 0;
        quickSort(sorted.clone(), 0, n - 1, true);
        System.out.printf("sorted input, n = %d, random pivot: %,12d comparisons (≈ 1.39·n·log₂n = %,d)%n", n, comparisons,
                (long) (1.39 * n * Math.log(n) / Math.log(2)));
    }
}