// Project: Patterns1
// Module: sorting1 Example
// Source code file: Main.java
// Traditional Sorting methods that
// implement InsertionSort, SelectionSort,
// and QuickSort.

public class Main {

    public static void main(String[] args) {

        int[ ] array = {45, 32, 11, 53, 45, 78, 9, 21};
        printArray(array);
        insertionSort(array, array.length);
        // Also try uncommenting the following
        // two sorting methods.
        // selectionSort(array, array.length);
        // quickSort(array, 0, array.length - 1);
        printArray(array);
    }

    public static void printArray(int[ ] a) {
        for(int n: a) {
            System.out.print(n + " ");
        }
        System.out.println( );
    }

    public static void insertionSort(
            int a[ ], int n) {

        for(int i = 1; i < n; i++) {
            int temp = a[i];
            int j;
            for(j = i; j > 0 && a[j - 1] > temp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = temp;
        }
    }

    public static void selectionSort(
            int a[ ], int n) {
        for(int i = 0; i < n; i++) {
            int min = i;
            for(int j = i + 1; j < n; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            // Swap a[j] and a[min]
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }

    // Quicksort is a recursive method.
    public static void quickSort(
            int[ ] a, int start, int end) {

        if (start < end) {
            int middle = partition(a, start, end);
            quickSort(a, start, middle - 1);
            quickSort(a, middle, end);
        }
    }

    public static int partition(
            int[ ] a, int p, int q) {

        int pivot = a[(p + q) / 2];
        while (p <= q) {
            while(a[p] < pivot) {
                p++;
            }
            while(pivot < a[q]) {
                q--;
            }
            if (p <= q) {
                int temp = a[p];
                a[p] = a[q];
                a[q] = temp;
                p++;
                q--;
            }
        }
        return p;
    }
}
// Output:
// 45 32 11 53 45 78 9 21
// 9 11 21 32 45 45 53 78