/*
    Sort.java
    CIS 160
    David Klick
    2015-09-19

    Demonstration of various sorting algorithms.
*/

public class Sort {
    public static void main(String[] args) {
        long startTime, elapsedTime;
        int array_size = 50000;
        final long RANGE = (long)Integer.MAX_VALUE - Integer.MIN_VALUE + 1;

        if (args.length > 0) {
            try {
                array_size = Integer.parseInt(args[0]);
                if (array_size < 10) array_size = 10;
            } catch (Exception e) {
                // ignore errors
            }
        }
        System.out.println("Sorting an array of " + array_size + " ints");
        int[] work = new int[array_size];
        int[] hold = new int[array_size];

        // create an array of random integers
        for (int i=0; i<hold.length; i++) {
            hold[i] = (int)(Math.random() * RANGE + Integer.MIN_VALUE);
        }

        // copy holding array to working array and do bubble sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "bubble");
        startTime = System.nanoTime();
        bubbleSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- bubble sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do my sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "my");
        startTime = System.nanoTime();
        mySort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- my sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do Jermey Wold's sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "Jermey Wold's");
        startTime = System.nanoTime();
        woldSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- my sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do selection sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "selection");
        startTime = System.nanoTime();
        selectionSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- selection sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do insertion sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "insertion");
        startTime = System.nanoTime();
        insertionSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- insertion sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do Shell sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "Shell");
        startTime = System.nanoTime();
        shellSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- Shell sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do merge sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "merge");
        startTime = System.nanoTime();
        mergeSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- merge sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do heap sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "heap");
        startTime = System.nanoTime();
        heapSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- heap sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do quick sort
        copyArray(hold, work);
        if (isSorted(work)) System.out.println("Error: array sorted before sort");
        System.out.printf("Sorting work array using %13s sort ", "quick");
        startTime = System.nanoTime();
        quickSort(work);
        elapsedTime = System.nanoTime() - startTime;
        if (!isSorted(work)) System.out.println("- quick sort failed!");
        else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);

        // copy holding array to working array and do Robsort/bogosort
        if (array_size < 12) {
            copyArray(hold, work);
            if (isSorted(work)) System.out.println("Error: array sorted before sort");
            System.out.printf("Sorting work array using %13s sort ", "Rob/bogo");
            startTime = System.nanoTime();
            robSort(work);
            elapsedTime = System.nanoTime() - startTime;
            if (!isSorted(work)) System.out.println("- Rob/bogo sort failed!");
            else System.out.printf("- elapsed time: %f sec\n", elapsedTime / 1000000000.0);
        }
    }
    public static void copyArray(int[] from, int[] to) {
        int max = from.length;
        if (max != to.length) {
            System.out.println("*** Warning: copyArray called with different length arrays ***");
            max = to.length;
        }
        for (int i=0; i<max; i++) to[i] = from[i];
    }

    public static boolean isSorted(int[] a) {
        for (int i=0; i<a.length-1; i++) {
            if (a[i] > a[i+1]) return false;
        }
        return true;
    }

    public static void mySort(int[] a) {
        int i, j, temp;
        int len = a.length;
        for (i=0; i<len-1; i++) {
            for (j = i+1; j<len; j++) {
                if (a[i] > a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    public static void bubbleSort(int[] a) {
        int i, j, temp;
        for (i=a.length-1; i>=0; i--) {
            for (j = 1; j <= i; j++) {
                if (a[j-1] > a[j]) {
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

    public static void woldSort(int[] a) {
        int i, j, k, temp;
        for (i=0; i<a.length-1; i++) {
            for (j=i+1; j<a.length; j++) {
                if (a[i] > a[j]) {
                    temp = a[j];
                    for (k=j; k>i; k--) a[k] = a[k-1];
                    a[i] = temp;
                }
            }
        }
    }

    public static void selectionSort(int[] a) {
        int i, j, min, temp;
        for (i=0; i<a.length-1; i++) {
            min = i;
            for (j=i+1; j<a.length; j++) {
                if (a[j] < a[min]) min = j;
            }
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

    public static void insertionSort(int[] a) {
        int i, j, temp;
        for (i=1; i<a.length; i++) {
            temp = a[i];
            j = i;
            while ((j>0) && (a[j-1] > temp)) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = temp;
        }
    }

    public static void shellSort(int[] a) {
        int i, j, incr, temp;
        incr = 3;
        while (incr > 0) {
            for (i=0; i<a.length; i++) {
                j = i;
                temp = a[i];
                while ((j >= incr) && (a[j-incr] > temp)) {
                    a[j] = a[j-incr];
                    j -= incr;
                }
                a[j] = temp;
            }
            if (incr/2 != 0) incr /= 2;
            else if (incr == 1) incr = 0;
            else incr = 1;
        }
    }

    public static void mergeSort(int[] a) {
        int[] tmp = new int[a.length];
        m_sort(a, tmp, 0, a.length-1);
    }


    private static void m_sort(int[] a, int[] tmp, int left, int right) {
        int mid;
        if (right > left) {
            mid = (right + left) / 2;
            m_sort(a, tmp, left, mid);
            m_sort(a, tmp, mid+1, right);
            merge(a, tmp, left, mid+1, right);
         }
    }

    private static void merge(int[] a, int[] tmp, int left, int mid, int right) {
        int i, left_end, num_elements, tmp_pos;
        left_end = mid - 1;
        tmp_pos = left;
        num_elements = right - left + 1;

        while ((left <= left_end) && (mid <= right)) {
            if (a[left] <= a[mid]) tmp[tmp_pos++] = a[left++];
            else tmp[tmp_pos++] = a[mid++];
        }

        while (left <= left_end) tmp[tmp_pos++] = a[left++];
        while (mid <= right) tmp[tmp_pos++] = a[mid++];

        for (i=0; i < num_elements; i++) {
            a[right] = tmp[right];
            right--;
        }
    }

    public static void heapSort(int[] a) {
        int len = a.length;
        for (int i=len/2; i>0; i--) siftDown(a, i, len);
        do {
            int tmp = a[0];
            a[0] = a[len-1];
            a[len-1] = tmp;
            len--;
            siftDown(a, 1, len);
        } while (len>1);
    }

    private static void siftDown(int[] a, int k, int bottom) {
        int tmp = a[k-1];
        while (k <= bottom/2) {
            int j = k + k;
            if ((j < bottom) && (a[j-1]<a[j])) j++;
            if (tmp >= a[j-1]) break;
            else {
                a[k-1] = a[j-1];
                k = j;
            }
        }
        a[k-1] = tmp;
    }

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

    private static void q_sort(int[] a, int left, int right) {
        int pivot, l_hold, r_hold;
        l_hold = left;
        r_hold = right;
        pivot = a[left];
        while (left < right) {
            while ((a[right] >= pivot) && (left < right)) right--;
            if (left != right) a[left++] = a[right];
            while ((a[left] <= pivot) && (left < right)) left++;
            if (left != right) a[right--] = a[left];
        }
        a[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot) q_sort(a, left, pivot-1);
        if (right > pivot) q_sort(a, pivot+1, right);
    }

    
    private static void robSort(int[] a) {
        while (!isSorted(a)) {
            for (int i=0; i<a.length; i++) {
                int x  = (int) (Math.random() * a.length);
                int y = (int) (Math.random() * a.length);
                int temp = a[x];
                a[x] = a[y];
                a[y] = temp;
            }
        }
    }
}

/*
    Sample output from two runs:

    Sorting an array of 50000 ints
    Sorting work array using        bubble sort - elapsed time: 4.140721 sec
    Sorting work array using            my sort - elapsed time: 3.872805 sec
    Sorting work array using Jermey Wold's sort - elapsed time: 0.478849 sec
    Sorting work array using     selection sort - elapsed time: 1.031056 sec
    Sorting work array using     insertion sort - elapsed time: 0.254015 sec
    Sorting work array using         Shell sort - elapsed time: 0.233544 sec
    Sorting work array using         merge sort - elapsed time: 0.010146 sec
    Sorting work array using          heap sort - elapsed time: 0.007975 sec
    Sorting work array using         quick sort - elapsed time: 0.008580 sec

    Sorting an array of 50000 ints
    Sorting work array using        bubble sort - elapsed time: 4.312357 sec
    Sorting work array using            my sort - elapsed time: 3.871998 sec
    Sorting work array using Jermey Wold's sort - elapsed time: 1.254090 sec
    Sorting work array using     selection sort - elapsed time: 1.030366 sec
    Sorting work array using     insertion sort - elapsed time: 0.252715 sec
    Sorting work array using         Shell sort - elapsed time: 0.231010 sec
    Sorting work array using         merge sort - elapsed time: 0.010194 sec
    Sorting work array using          heap sort - elapsed time: 0.007851 sec
    Sorting work array using         quick sort - elapsed time: 0.007948 sec
*/