package sorting;

import java.io.*;
import java.lang.Math;

public class SortShell5 {
// a sorting shell for experiments with the quicksort

public static void insertionSort (int [] a) {
// method to sort using the insertion sort
   for (int k = 1; k < a.length; k++) {
      int item = a[k];
      int i = k-1;
      while ((i >= 0) && a[i] > item){
         a[i+1] = a[i];
         i--;
      }
      a[i+1] = item;
   }
} // insertionSort

public static void quicksort (int [] a) {
// method to sort using the quicksort
    quicksortKernel (a, 0, a.length-1);
}

private static void quicksortKernel (int [] a, int first, int last) {
    int left=first+1;
    int right=last;
    int temp;

    while (right >= left) {
        // search left to find small array item
        while ((right >= left) && (a[first] <= a[right]))
            right--;
        // search right to find large array item
        while ((right >= left) && (a[first] >= a[left]))
            left++;
        // swap large left item and small right item, if needed
        if (right > left) {
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
    }
    // put a[first] in its place
    temp = a[first];
    a[first] = a[right];
    a[right] = temp;

    // recursively apply algorithm to a[first]..a[right-1] 
    // and a[right+1]..a[last], provided these segments contain >= 2 items
    if (first < right-1)
        quicksortKernel (a, first, right-1);
    if (right+1 < last)
        quicksortKernel (a, right+1, last);   
}

public static void refQuicksort (int [] a) {
// method to sort using the refined quicksort
    refQuicksortKernel (a, 0, a.length-1);
}

private static void refQuicksortKernel (int [] a, int first, int last) {
    int left=first+1;
    int right=last;
    int temp;

    // this part is new for a refined quicksort
    // begin by selecting a random integer, midIndex, between first and last,
    // and then swap a[first] with a[midIndex].
    int midIndex = first + (int)Math.floor((last-first)*Math.random());
    temp = a[first];
    a[first] = a[midIndex];
    a[midIndex] = temp;

    // refQuicksortKernel continues following the quicksort algorithm
    while (right >= left) {
        // search left to find small array item
        while ((right >= left) && (a[first] <= a[right]))
            right--;
        // search right to find large array item
        while ((right >= left) && (a[first] >= a[left]))
            left++;
        // swap large left item and small right item, if needed
        if (right > left) {
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
    }
    // put a[first] in its place
    temp = a[first];
    a[first] = a[right];
    a[right] = temp;

    // recursively apply algorithm to a[first]..a[right-1] 
    // and a[right+1]..a[last], provided these segments contain >= 2 items
    if (first < right-1)
        refQuicksortKernel (a, first, right-1);
    if (right+1 < last)
        refQuicksortKernel (a, right+1, last);   
}

    /** 
     * merge aInit[start1]..aInit[start1+mergeSize] with 
     *       aInit[start2]..Init[end2]
     *       with the result placed in aRes
     * Note:  it may be that start2 >= aInit.length, in which case, only the
     *        valide part of aInit[start1] is copied
     */
    private static void merge (int aInit [ ], int aRes [ ],
			       int start1, int start2, int end2) {
        /* Merge method not yet implemented */
    }	

    /** 
     * sort the array a, using a merge sort
     */
    public static  void  mergeSort (int initArr [ ]) {
	int resArr [ ] = new int [initArr.length];
	int a0[ ] = initArr;
	int a1[ ] = resArr;
	boolean needCopyBack = false;  
	
	int mergeSize = 1;
	int start1;
	while (mergeSize < initArr.length)
	    {
		int end2;
		for (start1 = 0; start1 < initArr.length; start1 = end2) {
		    int start2 = start1 + mergeSize;
		    end2 = start2 + mergeSize;
		    merge (a0, a1, start1, start2, end2);
		}

		// swap a0, a1 pointers, so a0 is starting array for next merge
		int temp [ ] = a0;
		a0 = a1;
		a1 = temp;
		mergeSize *= 2;

		// keep track of which array holds initArr object
		needCopyBack = !needCopyBack;
		
	    }

	//copy result into initArr, as needed
	if (needCopyBack)
	    {
		for (int i = 0; i < initArr.length; i++)
		    initArr [i] = a0 [i];
	    }
    }

    public static void main (String [] args) {

        System.out.printf ("%60s", "Algorithm Timings\n");
    System.out.println ("  Sort           Data Size   Ascending Data    "
                        + "Random Data     Descending Data");

    int size;
    long start_time, end_time;
    for (size = 10000; size < 700000; size *= 2)
        {
                
            //declaration of arrays
            int [] randData  = new int [size];
            int [] dataSet = new int [size];

            // initialize random array
            for (int i = 0; i < size; i++)
                randData[i] = (int)(Math.random()*4*size);

            /***************************************************/
            // insertion sort   insertion sort   insertion sort
            System.out.printf ("%-15s %7d", "Insertion", size);
            //ascending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*i;
            start_time = System.currentTimeMillis();
            insertionSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%12d", end_time-start_time);

            //random test
            for (int i = 0; i < size; i++)
                dataSet[i] = randData[i];
            start_time = System.currentTimeMillis();
            insertionSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%20d", end_time-start_time);

             //descending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*size - 2*i;
            start_time = System.currentTimeMillis();
            insertionSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%18d\n", end_time-start_time);
           
            /***************************************************/
            // quicksort   quicksort   quicksort   quicksort
            System.out.printf ("%-15s %7d", "Quicksort", size);
            //ascending test
            if (size > 30000)
                System.out.print("         ---");
            else {
                for (int i = 0; i < size; i++)
                    dataSet[i] = 2*i;
                start_time = System.currentTimeMillis();
                quicksort (dataSet); 
                end_time = System.currentTimeMillis();
                System.out.printf ("%12d", end_time-start_time);
            }
            
            //random test
            for (int i = 0; i < size; i++)
                dataSet[i] = randData[i];
            start_time = System.currentTimeMillis();
            //quicksort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%20d", end_time-start_time);

             //descending test
            if (size > 30000)
                System.out.print("               ---\n");
            else {
                for (int i = 0; i < size; i++)
                    dataSet[i] = 2*size - 2*i;
                start_time = System.currentTimeMillis();
                //quicksort (dataSet); 
                end_time = System.currentTimeMillis();
                System.out.printf ("%18d\n", end_time-start_time);
            }
            
             /***************************************************/
            // quicksort   quicksort   quicksort   quicksort
            System.out.printf ("%-15s %7d", "Ref. Quick.", size);
            //ascending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*i;
            start_time = System.currentTimeMillis();
            refQuicksort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%12d", end_time-start_time);

            //random test
            for (int i = 0; i < size; i++)
                dataSet[i] = randData[i];
            start_time = System.currentTimeMillis();
            refQuicksort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%20d", end_time-start_time);

             //descending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*size - 2*i;
            start_time = System.currentTimeMillis();
            refQuicksort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%18d\n", end_time-start_time);
           
             /***************************************************/
            // merge sort   merge sort   merge sort   merge sort
            System.out.printf ("%-15s %7d", "Merge Sort", size);
            //ascending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*i;
            start_time = System.currentTimeMillis();
            mergeSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%12d", end_time-start_time);

            //random test
            for (int i = 0; i < size; i++)
                dataSet[i] = randData[i];
            start_time = System.currentTimeMillis();
            mergeSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%20d", end_time-start_time);

             //descending test
            for (int i = 0; i < size; i++)
                dataSet[i] = 2*size - 2*i;
            start_time = System.currentTimeMillis();
            mergeSort (dataSet); 
            end_time = System.currentTimeMillis();
            System.out.printf ("%18d\n\n", end_time-start_time);     
        }
 
    } // main
} // SortShell5