Question

must provide the following public interface: 
public static void insertSort(int [] arr); 
public static void selectSort(int [] arr);
 public static void quickSort(int [] arr); 
public static void mergeSort(int [] arr); 
The quick sort and merge sort must be implemented by using recursive thinking. So the students may provide the following private static methods: 

//merge method 
//merge two sorted portions of given array arr, namely, from start to middle //and from middle + 1 to end into one sorted portion, namely, from start to end private static void merge(int [] arr, int start, int middle, int end);
//merge sort recursive version 
//sort the portion of giving array arr, from begin to end private static void mergeSortRecursive(int [] arr, int begin, int end);
 //find pivot point for quick sort private static int pivot(int [] arr, int begin, int end);
 //quick sort recursive version 
//sort the portion of giving array arr, from begin to end private static void quickSortRecursive(int [] arr, int begin, int end);
 The student need to have and only have the above public and private static methods in his/her implementation of MySort class.


/**
 * CSCI463ProjOne. This is the main function for Project One.
 * This class is given to students.
 * 
 * @author 
 * @version 
 */
import java.util.*;

public class CSCI463ProjOne
{
    public static final int RANGE = 100000;
    
    /**
     * Randomly fill up the given array with integers from 0 to 100000
     */
    public static void fillArray(int [] arr)
    {
        Random randGen = new Random();
        for(int i = 0; i < arr.length; i++)
            arr[i] = randGen.nextInt(RANGE);
    }
    
    /**
     * copy the content in second array to first array. We assume 
     * two array has same size
     * @param firstArray the destination of copy action
     * @param secondArray the source of copy action
     */
    public static void copy(int [] firstArray, int [] secondArray)
    {
        for(int i = 0; i < secondArray.length; i++)
            firstArray[i] = secondArray[i];
    }
    /**
     * isSorted
     * @return true if the array is sorted from least to largest
     * or is sorted from largest to least
     */
    public static boolean isSorted(int [] arr)
    {
        if(arr.length <= 1) return true;
        int index = 0;
        while(index < arr.length-1 && arr[index] == arr[index+1])
        {
            index++;
        }
        // bypass first equal elements
        if(index == arr.length - 1) return true; // all elements are the same
        else if(index < arr.length - 1 && arr[index] > arr[index+1]) // possible descend
        {
            for(int i = index+2; i < arr.length; i++)
                if(arr[i] > arr[i-1]) return false;
        }
        else // sort for ascend
        {
             for(int i = index+2; i < arr.length; i++)
                if(arr[i] < arr[i-1]) return false;
        }
        
        return true;
    }
    
    /**
     * test the sort with given array. The test array will not be modified
     * @param arr The array that is used to test the sort. The array will not be modified
     * @name The name of sort method that is to be tested
     */
    public static void testSort(int [] arr, String name)
    {
        long totalTime = 0;
        int [] a = new int[arr.length];
        copy(a, arr); // copy arr to a
        
        // get start time
        long start = Calendar.getInstance().getTimeInMillis();
        if(name.equals("Insert Sort"))
            MySorts.insertSort(a);
        else if(name.equals("Select Sort"))
            MySorts.selectSort(a);
        else if(name.equals("Quick Sort"))
            MySorts.quickSort(a);
        else if(name.equals("Merge Sort"))
            MySorts.mergeSort(a);
            
        long end = Calendar.getInstance().getTimeInMillis();
        if(isSorted(a)){
            totalTime = end - start;
            System.out.println("Execution time for " + name + " is: " + totalTime + " milliseconds");
        }
        else
            System.out.println("The " + name + " did not work properly");
    }
    
    /**
     * display the test menu
     */
    public static void displayMenu()
    {
        System.out.println("***************************");
        System.out.println("*          MENU           *");
        System.out.println("* 1. Fill Array           *");
        System.out.println("* 2. Select Sort          *");
        System.out.println("* 3. Insert Sort          *");
        System.out.println("* 4. Quick Sort           *");
        System.out.println("* 5. Merge Sort           *");
        System.out.println("* 6. Quit                 *");
        System.out.println("***************************");
    }
    
    public static void main(String [] args){
        int choice;
        int [] arr = new int[RANGE];
        
        Scanner input = new Scanner(System.in);
        do{
            displayMenu();
            System.out.println("Enter you choice: ");
            choice = input.nextInt();
            switch(choice){
                case 1: // generate a new random filled array
                    fillArray(arr);
                    break;
                case 2: // select sort
                    testSort(arr, "Select Sort");
                    break;
                case 3: // insert sort
                    testSort(arr, "Insert Sort");
                    break;
                case 4: // quick sort
                    testSort(arr, "Quick Sort");
                    break;
                case 5: // merge sort
                    testSort(arr, "Merge Sort");
                    break;
                case 6: // quit
                    System.out.println("Make sure that you have good documentation!");
                    break;
                default: // wrong choice
                    
            }
            
        }while(choice != 6);
    }
   
}

Answer 1

public class Main {

/*
Method to sort array data using selection sort
arr[] --> Array to be sorted
*/
public static void selectSort(int[] arr) {

for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;

int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return;
}
/*
Method to sort array data using insertion sort
arr[] --> Array to be sorted
*/
public static int[] insertSort(int[] input) {

int temp;
for (int i = 1; i < input.length; i++) {
for (int j = i; j > 0; j--) {
if (input[j] < input[j - 1]) {
temp = input[j];
input[j] = input[j - 1];
input[j - 1] = temp;
}
}
}
return input;
}

/* Pivot and partitioning function: Takes last element as pivot,places the pivot element at its correct
position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right
of pivot */
private static int pivot(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
public static void quickSortRecursive(int arr[], int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = pivot(arr, low, high);

// Recursively sort elements before
// partition and after partition
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}

// merge two sorted portions of given array arr, namely, from start to middle
// and from middle + 1 to end into one sorted portion, namely, from start to end
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
private static void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
public static void mergeSortRecursive(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves
mergeSortRecursive(arr, l, m);
mergeSortRecursive(arr, m + 1, r);

merge(arr, l, m, r);
}
}
/*
Main method
*/
public static void main(String a[]) {
System.out.print("Selection sort results:\n ");
int[] arr1 = {24,2,45,20,56,75,2,56,99,53,12};
selectSort(arr1);
for (int i: arr1) {
System.out.print(i);
System.out.print(", ");
}
System.out.print("\nInsertion sort results:\n ");
int[] arr2 = {10,34,2,56,7,67,88,42};
insertSort(arr2);
for (int i: arr2) {
System.out.print(i);
System.out.print(", ");
}
int arr3[] = {10, 7, 8, 9, 1, 5};
int n = arr3.length;
System.out.print("\nQuick sort results:\n ");
quickSortRecursive(arr3, 0, n - 1);
for (int i: arr3) {
System.out.print(i);
System.out.print(", ");
}
  
int arr4[] = {12, 11, 13, 5, 6, 7};
int arr_size = arr4.length;
System.out.print("\nMerge sort results:\n ");
mergeSortRecursive(arr4, 0, arr_size - 1);
for (int i: arr4) {
System.out.print(i);
System.out.print(", ");
}
}
}