import java.util.Arrays;

/** Four small, in-place teaching implementations. Non-null int arrays only. */
public final class Sorting {
    private Sorting() { }

    // region selection
    public static void selectionSort(int[] a) {
        for (int i = 0; i + 1 < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) min = j;
            }
            swap(a, i, min);
        }
    }
    // endregion selection

    // region insertion
    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
    // endregion insertion

    // region bubble
    public static void bubbleSort(int[] a) {
        for (int end = a.length - 1; end > 0; end--) {
            boolean changed = false;
            for (int j = 0; j < end; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    changed = true;
                }
            }
            if (!changed) return;
        }
    }
    // endregion bubble

    // region quick
    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }

    private static 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 static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int boundary = lo;
        for (int scan = lo; scan < hi; scan++) {
            if (a[scan] < pivot) {
                swap(a, boundary, scan);
                boundary++;
            }
        }
        swap(a, boundary, hi);
        return boundary;
    }
    // endregion quick

    // region swap
    private static void swap(int[] a, int i, int j) {
        if (i == j) return;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // endregion swap

    public static void main(String[] args) {
        int[] a = {7, 3, 5, 3, 9, 1};
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
}