/*
 * This is a summary of sorting routines that make the AP
 * folks happy.  Note that there is generally more
 * than one way to write each of these, so if you
 * like your way of writing one of them better than
 * what you see here, that's fine.
 *
 * I suggest that you use this code to understand the
 * mechanics of how each sort works.  To keep it simple,
 * try tracing each sort by hand on each of the following
 * arrays:
 *
 * { 3, 6, 1, 5, 2, 4 }
 * { 6, 5, 4, 3, 2, 1 }
 *
 * Try to keep track of the number of comparisons done
 * between elements in the array and the number of times
 * elements are swapped.  (Treat temp = a, a = b, b = temp
 * as one swap for simplicity.)
 *
 * For heapsort and mergesort, you may wish to try a
 * somewhat larger set of data, say:
 * 
 * { 7, 12, 9, 2, 3, 11, 1, 8, 6, 10, 5, 4 }
 *
 * I have intentionally left no documentation.
 * I'd like you to be able to explain to me what happens
 * when this code executes in terms of how the state of
 * the array is altered as it goes from being unsorted to sorted.
 * Also be able to explain the order of growth as the number
 * of elements, n, gets larger.  It's easy enough to simply
 * state that bubble sort is O(n2), but I want to hear
 * your rationale for why.
 */

// QUICK SORT

void quicksort(int[] a) {
    quick(a, 0, a.length-1);
}
    
void quick(int[] a, int left, int right) {
    if (right > left) {
        int pivotPos = partition(a, left, right);
        quick(a, left, pivotPos-1);
        quick(a, pivotPos+1, right);
    }
}
    
int partition(int[] a, int left, int right) {
    int splitPos = left;
    for (int i = left; i < right; i++) {
        if (a[i] < a[right]) {
            swap(a, i, splitPos);
            splitPos++;
        }
    }
    swap(a,splitPos,right);
    return splitPos;
}

void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
    
// MERGE SORT

// Algorithm taken from H.W. Lang, FH Flensburg 
// (http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm)
public static void mergesort(int[] arr) {
    ms(arr, 0, arr.length-1);
}
    
private static void ms(int[] a, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        ms(a, low, mid);
        ms(a, mid+1, high);
        merge(a, low, mid, high);
    }
}

private static void merge (int[] a, int low, int mid, int high) {
    int[] b = new int[a.length];
    int i, j, k;

    for (i = low; i <= high; i++)
        b[i]=a[i];

    i = low; j = mid+1; k = low;
    while (i <= mid && j <= high)
        if (b[i]<=b[j])
            a[k++]=b[i++];
        else
            a[k++]=b[j++];

    while (i <= mid)
        a[k++]=b[i++];
}

// BUBBLE SORT

void bubbleSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length - i - 1; j++) {
            if (a[j] > a[j+1]) {
                swap(a, j, j+1);
            }
        }
    }
}
    
// INSERTION SORT

void insertionSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        insert(a, i);
    }
}

void insert(int[] a, int i) {
    int j;
    for (j = 0; a[i] > a[j] && j < i; j++) {}
    int temp = a[i];
    for (int k = i; k > j; k--) {
        a[k] = a[k-1];
    }
    a[j] = temp;
}
    
// SELECTION SORT

void selectionSort(int[] a) {
    int min, minPos;
    for (int i = 0; i < a.length; i++) {
        min = a[i];
        minPos = i;
        for (int j = i; j < a.length; j++) {
            if (a[j] < min) {
                min = a[j];
                minPos = j;
            }
        }
        swap(a, i, minPos);
    }
}

// HEAP SORT

    // Note the use of modular, top-down programming
    // We know that heapsort needs to build a heap and then sort it,
    // so why not write that as code and then fill in the needed methods?
    public static void heapsort(int[]a) {
        buildHeap(a);
        sortHeap(a);
    }
        
    // I let the other methods be private to make a point about public.
    // The only method that should be visible if you want to do heapsort
    // is the heapsort method itself.  Unless you have a reason to let
    // a method like buildheap be visible outside this class, it probably
    // should be private.  That said, the AP graders are expecting public
    // methods and private instance variables; on the actual test, use
    // public everywhere for methods unless instructed otherwise.
    
    // Trickle hasn't been written, but building the heap is the process
    // of going through the array, right to left, and performing trickle
    // at each place.
    private static void buildHeap(int[] a) {
        for (int i = a.length-1; i >= 0; i--) {
            trickle(a, i, a.length);
        }
    }

    // Swap the root with the last unsorted position
    // Then trickle the new root to maintain a heap
    private static void sortHeap(int[] a) {
        for (int i = a.length-1; i >= 0; i--) {
            swap(a, 0, i);
            trickle(a, 0, i);
        }
    }
        
    // The game plan:
    // * If a node has no children, done
    // * If a node has one child, check to see if a swap is needed
    // * If a node has two children, check to see which is bigger and if a swap is needed
    private static void trickle(int[] a, int i, int lastPosition) {
        // max contains the bigger child datum
        // maxPos contains the place in the array where the bigger child datum is contained
        int max = 0, maxPos = 0;
        if (hasChildren(i, lastPosition)) {
            if (hasOnlyLeftChild(i, lastPosition)) { 
                max = a[left(i)];
                maxPos = left(i);
            } else {
                maxPos = (a[left(i)] > a[right(i)]) ? left(i) : right(i);
                max = a[maxPos];
            }
            // Now determine if a swap is warranted
            // Note that lastPosition holds the biggest array index into which
            // a datum can be trickled.  We don't want to trickle into something
            // that is already sorted!
            if (max > a[i]) {
                swap(a, i, maxPos);
                trickle(a, maxPos, lastPosition);
            }
        }
    }

    // A slew of helper functions to get the details done
    // Sometimes it is easier to identify some of these and write them
    // before writing the higher-level stuff.  Deciding what to write
    // first can be an art form.
    private static int left(int x) { return 2*x + 1; }
    private static int right(int x) { return 2*x + 2; }
    private static int parent(int x) { return (x-1) / 2; }
    
    private static void swap(int[] arr, int i1, int i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }
        
    private static boolean hasChildren(int index, int length) {
        // Imagine a binary number.  Shifting all of the 1s to the right
        // by a position is the same thing as dividing by two.  It also
        // behaves as integer arithmetics as if there is a one in the 
        // rightmost position, it gets shifted out of existence.
        // No critical reason to do it this way, just wanted to show it.
        return (index+1 <= (length >> 1));
    }

    private static boolean hasOnlyLeftChild(int index, int length) {
        return ((index*2)+2 == length);
    }

    
// Pretty printing procedure for arrays of integers

void printArray(int[] a) {
    System.out.print("{ " + a[0]);
    for (int i = 1; i < a.length; i++) {
        System.out.print(", " + a[i]);
    }
    System.out.println(" }");
}