package strategy;

public class QuickSort implements SortStrategy {
    @Override
    public void sort(int[] data) {
        System.out.println("  [QuickSort] O(n log n) avg — fast in practice, not stable");
        quickSort(data, 0, data.length - 1);
    }

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

    private int partition(int[] a, int lo, int hi) {
        int pivot = a[hi], i = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] <= pivot) { int t = a[i]; a[i++] = a[j]; a[j] = t; }
        int t = a[i]; a[i] = a[hi]; a[hi] = t;
        return i;
    }

    @Override public String getName() { return "QuickSort"; }
}