import java.util.Arrays;
import java.util.Random;

public class Sort {

    private static Random random;

    public static <T extends Comparable<? super T>> void insertionSort(T[] a) {
        for (int j = 1; j < a.length; ++j) {
            assert isSorted(a, 0, j - 1);
            T key = a[j];
            int i = j - 1;
            while(i >= 0 && (a[i].compareTo(key) > 0)) {
                a[i + 1] = a[i];
                i = i - 1;
            }
            a[i + 1] = key;
        }
    }

    private static <T extends Comparable<? super T>>
            boolean isSorted(T[] array, int start, int end) {
        for (int i = start; i < end; ++i) {
            if (!(array[i].compareTo(array[i + 1]) < 0))
                return false;
        }
        return true;
    }

    public static <T extends Comparable<? super T>> void quickSort(T[] a) {
        qs(a, 0, a.length - 1);
    }

    private static <T extends Comparable<? super T>>
            void qs(T[] a, int begin, int end) {
        if (begin >= end) { // Base case: nothing to sort
            return;
        }
        int pivot = partition(a, begin, end);
        qs(a, begin, pivot - 1);
        qs(a, pivot + 1, end);
    }

    private static <T extends Comparable<? super T>>
            int partition(T[] a, int begin, int end) {
        T pivotValue = a[end];
        int i = begin - 1;
        for (int j = begin; j <= end - 1; j++) {
            if (a[j].compareTo(pivotValue) <= 0) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, end);
        return i + 1;
    }

    private static <T> void swap(T[] a, int i, int j) {
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    // Why isn't something like this in Arrays, like Collections.shuffle()?
    public static <T> void shuffle(T[] array) {
        if (random == null) { random = new Random(); }
        int count = array.length;
        for (int i = count; i > 1; i--) {
            swap(array, i - 1, random.nextInt(i));
        }
    }

    public static void main(String[] args) {
        Integer[] a = {5, 2, 4, 6, 1, 3};
        System.out.println("Unsorted aray: " + Arrays.toString(a));
        insertionSort(a);
        System.out.println("Insertion-sorted aray: " + Arrays.toString(a));

        shuffle(a);
        System.out.println("Shuffled aray: " + Arrays.toString(a));
        quickSort(a);
        System.out.println("Quicksorted aray: " + Arrays.toString(a));

    }

}