lab 25.2

import chn.util.*;
import apcslib.Format;
import java.util.*;
/**
 * Description of the Class
 *
 * @David Cortes
 * @Right Now, 2015
 */
class Sorts
{
    private static long steps = 0;
    /**
     * Will sort a list of integers from least to greatest using
     * bubble sort method
     *
     * @param list list of random integers to be sorted
     */
    public static void bubbleSort(int[] list)
    {
        steps ++;          //initialization of outer loop
        for (int outer = 0; outer < list.length - 1; outer++)
        {
            steps += 3; //boundary check, increment, initialization of inner loop
            for (int inner = 0; inner < list.length-outer-1; inner++)
            {
                steps += 3;    //boundary check, increment, if comparison
                if (list[inner] > list[inner + 1])
                {
                    //swap list[inner] & list[inner+1]
                    int temp = list[inner];
                    list[inner] = list[inner + 1];
                    list[inner + 1] = temp;
                    steps += 3;    //swaping values
                }
            }
        }
    }

    /**
     * Will sort a list of integers from least to greatest using
     * selection sort method
     *
     * @param list list of random integers to be sorted
     */
    public static void selectionSort(int[] list)
    {
        int min, temp;
        steps ++; //initialization of outer loop
        for (int outer = 0; outer < list.length - 1; outer++)
        {
            steps += 4; //boundary check, increment, intitialization of inner loop
            min = outer;
            for (int inner = outer + 1; inner < list.length; inner++)
            {
                steps +=3; //boundary check, increment, if comparison
                if (list[inner] < list[min])
                {
                    min = inner; // a new smallest item is found
                    steps ++;;
                }
            }
            //swap list[outer] & list[min]
            temp = list[outer];
            list[outer] = list[min];
            list[min] = temp;
            steps +=3;
        }
    }

    /**
     * Will sort a list of integers from least to greaetest using
     * insertion sort method
     *
     * @param list list of random integers
     */
    public static void insertionSort(int[] list)
    {
        steps++; //initialization of outer loop
        for (int outer = 1; outer < list.length; outer++)
        {
            int position = outer;
            int key = list[position];
            // Shift larger values to the right
            steps +=5; //initialization of while loop
            while (position > 0 && list[position - 1] > key)
            {
                list[position] = list[position - 1];
                position--;
                steps++;
            }
            list[position] = key;
            steps++;
        }
    }

    /**
     * Takes in entire vector, but will merge the following sections
     * together: Left sublist from a[first]..a[mid], right sublist from
     * a[mid+1]..a[last]. Precondition: each sublist is already in
     * ascending order
     *
     * @param a Description of Parameter
     * @param first Description of Parameter
     * @param mid Description of Parameter
     * @param last Description of Parameter
     */
    private static void merge(int[] a, int first, int mid, int last)
    {
        int[] temp = new int[a.length+1];
        int aMark = 0, bMark = mid +1;
        for(int i = 0; i<a.length; i++){
            if(aMark==mid && bMark < last) {
                temp[i] = a[bMark];
                bMark++;
            }
            else if(bMark == last && aMark < mid) {
                temp[i] = a[aMark];
                aMark++;
            }
            else if(aMark < mid && bMark<last) {
                if(a[aMark] < a[bMark]) {
                    temp[i] = a[aMark];
                    aMark++;
                }
                else {
                    temp[i] = a[bMark];
                    bMark++;
                }
            }

        }
        a = temp;
    }

    /**
     * Description of the Method
     *
     * @param a Description of Parameter
     * @param first Description of Parameter
     * @param last Description of Parameter
     */
    public static void mergeSort(int[] a, int first, int last)
    {
        int temp;
        int mid;
        if(last - first ==0){
        }
        else if(last - first == 1){
            if(a[first] >= a[last]){
                temp = a[first];
                a[first] = a[last];
                a[last] = temp;
            }
        }

        else
        {
            mid = (first + last)/2;
            mergeSort(a, first, mid);
            mergeSort(a, mid+1, last);
            merge(a, first, mid+1, last);

        }
    }

    /**
     * Description of the Method
     *
     * @param list Description of Parameter
     * @param first Description of Parameter
     * @param last Description of Parameter
     */
    public static void quickSort(int[] list, int first, int last)
    {
        int g = first, h = last;
        int midIndex = (first + last) / 2;
        int dividingValue = list[midIndex];
        steps +=5;
        do
        {
            while (list[g] < dividingValue) g++;
            while (list[h] > dividingValue) h--;
            steps +=2;
            if (g <= h)
            {
                //swap(list[g], list[h]);
                int temp = list[g];
                list[g] = list[h];
                list[h] = temp;
                g++;
                h--;
                steps +=5;
            }
        }
        while (g < h);
        if (h > first){
            quickSort (list,first,h);
            steps++;
        }
        if (g < last){
            quickSort (list,g,last);
            steps++;
        }
        steps +=2;
    }

    /**
     * Accessor method to return the current value of steps
     *
     */
    public static long getStepCount()
    {
        return steps;
    }

    /**
     * Modifier method to set or reset the step count. Usually called
     * prior to invocation of a sort method.
     *
     * @param stepCount value assigned to steps
     */
    public static void setStepCount(int stepCount)
    {
        steps = stepCount;
    }
}
/**
 * Description of the Class
 *
 * @author G. Peck
 * @created July 18, 2002
 */
public class SortStep
{
    private ConsoleIO console = new ConsoleIO ();
    private int[] myArray;
    /**
     * Initializes myArray with random integers in the range
     * 1..largestInt
     *
     * @param numInts number of integers to generate (size of myArray)
     * @param largestInt largest possible random integer to create
     */
    private void fillArray(int numInts, int largestInt)
    {
        myArray = new int[numInts];
        Random randGen = new Random();
        for (int loop = 0; loop < myArray.length; loop++)
        {
            myArray[loop] = randGen.nextInt(largestInt) + 1;
        }
    }

    /**
     * prints out the contents of the array in tabular form, 12 columns
     */
    private void screenOutput()
    {
        for (int loop = 0; loop < myArray.length; loop++)
        {
            if (loop % 12 == 0)
            {
                System.out.println();
            }
            System.out.print(Format.right(myArray[loop], 6));
        }
        System.out.println();
    }

    /**
     * The program asks the user to select a sorting algorithm,
     * fills the array with an amount of data chosen by the user,
     * calls the sorting algorithm, and gives an option of printing
     * out the data after it has been sorted.
     */
    public void sortMenu()
    {
        String choice;
        String print;
        do
        {
            System.out.println();
            System.out.println("Sorting algorithm menu");
            System.out.println();
            System.out.println("(1) Bubble sort");
            System.out.println("(2) Selection sort");
            System.out.println("(3) Insertion sort");
            System.out.println("(4) Recursive mergesort");
            System.out.println("(5) Quicksort");
            System.out.println("(Q) Quit");
            System.out.println();
            System.out.print("Choice ---> ");
            choice = console.readLine() + " ";
            if ('1' <= choice.charAt(0) && choice.charAt(0) <= '5')
            {
                System.out.println();
                System.out.print("How many numbers do you wish to generate? ");
                int numInts = console.readInt();
                System.out.print("Largest integer to generate? ");
                int largestInt = console.readInt();
                fillArray(numInts, largestInt);
                Sorts.setStepCount(0);
                switch (choice.charAt(0))
                {
                    case '1':
                    Sorts.bubbleSort(myArray);
                    break;
                    case '2':
                    Sorts.selectionSort(myArray);
                    break;
                    case '3':
                    Sorts.insertionSort(myArray);
                    break;
                    case '4':
                    Sorts.mergeSort(myArray, 0, myArray.length - 1);
                    break;
                    case '5':
                    Sorts.quickSort(myArray, 0, myArray.length - 1);
                    break;
                }
                System.out.println();
                System.out.print("Print list to screen (y/n)? ");
                print = console.readLine();
                if (print.charAt(0) == 'y' || print.charAt(0) == 'Y')
                {
                    screenOutput();
                }
                System.out.println();
                System.out.println("# steps = " + Sorts.getStepCount());
                System.out.println();
                System.out.print("Hit return to continue");
                console.readLine();
            }
        } while (choice.charAt(0) != 'Q' && choice.charAt(0) != 'q');
    }

    /**
     * Sorting Step Count Template:
     * Provides a main method for access to the sorting menu
     *
     * @param args The command line arguments - not used
     */
    public static void main(String[] args)
    {
        SortStep doSorts = new SortStep();
        doSorts.sortMenu();
    }
}