/**
 * A utility class defining a variety of sorting algorithms.
 * 
 * @author Lyndon While, Rachel Cardell-Oliver
 * @version May 2015, May 2017
 */
import java.util.*;

public class Sorter
{
    public Sorter(int testsize)
    {
        int noOfAlgorithms = 6;
        int[][] a = new int[noOfAlgorithms][testsize];
        for (int i = 0; i < testsize; i++)
            a[0][i] = i;
        shuffle(a[0]);
        for (int i = 1; i < noOfAlgorithms; i++)
            a[i] = Arrays.copyOf(a[0], testsize);
        for (int j = 1; j < noOfAlgorithms; j++) 
        {
            for (int i = 0; i < j; i++)
                assert a[j] != a[i] : "Algorithms " + i + " and " + j + " have the same array object";
            assert Arrays.equals(a[j], a[0]) : "Algorithm " + j + " has the wrong values";
        }
        long[] times = new long[noOfAlgorithms + 1];
        times[0] = System.nanoTime();
        bubbleSort(a[0]);
        times[1] = System.nanoTime();
        selectionSort(a[1]);
        times[2] = System.nanoTime();
        insertionSort(a[2]);
        times[3] = System.nanoTime();
        quickSort(a[3]);
        times[4] = System.nanoTime();
        quickSortM(a[4]);
        times[5] = System.nanoTime();
        mergeSort(a[5]);
        times[6] = System.nanoTime();
        for (int j = 1; j < noOfAlgorithms; j++) 
            assert Arrays.equals(a[j], a[0]) : "Algorithm " + j + " failed";
        for (int i = 0; i < noOfAlgorithms; i++)
            System.out.println((times[i + 1] - times[i]) / 1000000 + "ms");
    }

    // shuffles a randomly 
    private void shuffle(int[] a)
    {
        Random r = new Random();
        for (int i = 0; i < a.length - 1; i++)
            swap(a, i, i + r.nextInt(a.length - i));
    }

    // Bubble sort works by repeatedly exchanging adjacent elements of a 
    public static void bubbleSort(int[] a)
    {
        for (int pass = 1; pass < a.length; pass++)
            for (int j = 0; j < a.length - pass; j++)
                if (a[j] > a[j + 1])
                    swap(a, j, j+1);
    }

    // Selection sort works by finding the smallest element of a, then the next smallest, etc. 
    public static void selectionSort(int[] a)
    {
        for (int pass = 0; pass < a.length - 1; pass++)
        {
            int smallest = pass;
            for (int j = pass + 1; j < a.length; j++)
                if (a[j] < a[smallest])
                    smallest = j;
            swap(a, smallest, pass);
        }
    }

    // Insertion sort works by sorting the front n elements of a, 
    // then inserting the (n+1)th element in its correct place
    public static void insertionSort(int[] a)
    {
        for (int pass = 1; pass < a.length; pass++)
        {
            int tmp = a[pass];
            int pos = pass - 1;
            while (pos >= 0 && a[pos] > tmp)
            {
                a[pos + 1] = a[pos];
                pos--;
            }
            a[pos + 1] = tmp;
        }
    }

    /**
     * Quicksort works by splitting a into sublists smaller and bigger than the pivot, 
     * then sorting each of these lists recursively
     * @param a array to be sorted (in place)
     */
    public static void quickSort(int[] a)
    {
         qsort(a, 0, a.length - 1);
    }

    /**
     * quicksort of a[l..u] inclusive
     * @param a array to be sorted
     * @param l lower bound to sort from
     * @param u upper bound to sort to
     * @returns p, position of pivot  
     */
    private static void qsort(int[] a, int low, int high)
    {
        if (low < high) // if low == high, there's only one element
        {
            int p = partition(a, low, high); 
            qsort(a, low, p - 1);
            qsort(a, p + 1, high); 
        }
    }
    
    /**
     * Implementation of the partition function that always uses last element a[u] 
     * as the pivot. This method rearranges a such that all elements before pivot at a[p] are smaller,
     * and all elements after p are bigger.
     * @param a array to be sorted
     * @param l lower bound to sort from
     * @param u upper bound to sort to, pivot chosen as element at this position
     * @returns p, position of pivot  
     */
    private static int partition(int[] a, int low, int high)
    {
        // this code always uses the last element a[high] as the pivot 
        int si = low;
        for (int i = low; i < high; i++) {
            if (a[i] <= a[high]) { 
                swap(a, i, si++);   // swap small elements to the front 
            }
        }
        swap(a, si, high);   // swap the pivot to be between the smalls and the larges
        return si;
    }


  
     /*
     * Another implementation of quicksort with a different pivot selection
     * @param a array to be sorted
     * @param l lower bound to sort from
     * @param u upper bound to sort to
     */
    public static void quickSortM(int[] a)
    {
        qsortM(a, 0, a.length - 1);     
    }
    
    
    /*
     * Quicksort with partitioning around middle element pivot 
     * @param a array to be sorted
     * @param l lower bound to sort from
     * @param u upper bound to sort to
     * @param p position of the pivot (must have l<=p<=u)
     * @returns p, position of pivot  
     */
    private static void qsortM(int[] a, int l, int u)
    {
        int pivotValue = a[(l+u)/2]; //pivot is middle of the array
        int i=l; //start low partition from the left
        int j=u; //start high partition from the right

        while (i<=j) //until all elements are in position
        {
            while (a[i] < pivotValue)
            {
                i++; //skip over in place elements
            }
            while (a[j] > pivotValue)
            {
                j--; //skip over in place elements
            }
            if (i<=j) //swap out of place elements
            {
                swap(a,i++,j--);
            }
        }

        if (l<j) {
            qsort(a,l,j);
        }
        if (i<u) {
            qsort(a,i,u);
        }
    }
        
 

    /**
     * Mergesort works by sorting the front and back halves of a, then merging these sorted sublists
     * note that mergesort cannot be done in-place
     */
    public static void mergeSort(int[] a)
    {
        msort(a, 0, a.length - 1);
    }

    // Mergesorts a[l..u] inclusive
    private static void msort(int[] a, int l, int u)
    {
        if (l < u)// if l == u, there's only one element
        {
            int m = (l + u) / 2;
            msort(a, l, m);
            msort(a, m + 1, u);
            merge(a, l, m, u);
        }
    }

    // merges a[l..m] with a[m+1..u] via b, assuming they are both ordered
    private static void merge(int[] a, int l, int m, int u)
    {
        while (l <= m && a[l] <= a[m + 1]) l++;     // small elements on the first list needn't be moved
        if (l <= m)                                 // if the first list is exhausted, we're done
        {
            while (u >= m + 1 && a[u] >= a[m]) u--; // large elements on the second list needn't be moved
            int start = l;                          // record the start and finish points of the first list
            int finish = m++;
            int[] b = new int[u - l + 1];           // this is where we will put the sorted list
            int z = 0;
            while (m <= u)                          // while the second list is alive, copy the smallest element
                if (a[l] <= a[m]) b[z++] = a[l++];
                else              b[z++] = a[m++];
            while (z < b.length)  b[z++] = a[l++];                  // copy the rest of the first list to b
            for (int i = 0; i < b.length; i++) a[start + i] = b[i]; // copy the sorted list back from b
        }
    }

    // swaps a[i] and a[j] 
    private static void swap(int[]a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    // linear search of an array
    // returns the index of the first occurrence of x, or -1 if none found 
    public static int linearSearch(int[] a, int x)
    {
        for (int i = 0; i < a.length; i++)
            if (a[i] == x) 
                return i;
        return -1;
    }

    // binary search of a sorted array
    // returns the index of any occurrence of x, or -1 if none found 
    public static int binarySearch(int[] a, int x)
    {
        int l = 0;
        int u = a.length - 1;
        while (l <= u)
        {
            int m = (l + u) / 2;
            if (a[m] == x)
                return m;
            else 
            if (a[m] < x)
                l = m + 1;
            else
            // a[m] > x 
                u = m - 1;
        }
        return -1;
    }
}