// File: A3Driver.java

// Author: Geoffrey Tien/ Rita Ester

// Date: 2017-10-06

// Description: Simple test driver for CSCI 225 Assignment #3

// This file does not need to be modified

// Please ensure that the input files are in your

// project "bin" directory with the compiled class files.

// In Eclipse: The input files need to be imported

// to the project folder for this project.

import java.io.*;

import java.util.ArrayList;

import java.util.Scanner;

public class A3Driver

{

static final int SELECTION_ = 0;

static final int INSERTION_ = 1;

static final int QUICK_ = 2;

static final int MERGE_ = 3;

static final int SHELL_ = 4;

public static void main(String[] args)

{

selectionSortTest();

insertionSortTest();

quickSortTest();

mergeSortTest();

shellSortTest();

}

// Checks that every element of original array is in the sorted array

public static boolean contains(Comparable[] original, Comparable[] sortedArray)

{

boolean contains = true;

for (int i = 0; i

{

contains = contains && linearSearch(sortedArray, original[i]);

}

return contains;

}

// Linear search used in case target array is improperly isSorted

public static boolean linearSearch(Comparable[] arr, Comparable item){

boolean found = false;

for (int i = 0; i

found = arr[i].equals(item);

return found;

}

// Checks that an array is sorted in ascending order

public static boolean isSorted(Comparable[] arr){

boolean sorted = true;

if (arr.length

else {

for (int i = 0; i

sorted = sorted && arr[i].compareTo(arr[i+1])

}

return sorted;

}

// automated test method for Selection Sort

private static void selectionSortTest(){

try {

System.out.println(" SELECTION SORT --------------");

Integer[] arr1 = (Integer[])readInput("test1.txt", 1);

System.out.print("Test 1: ");

displayTestResult(arr1, SELECTION_);

Double[] arr2 = (Double[])readInput("test2.txt", 2);

System.out.print("Test 2: ");

displayTestResult(arr2, SELECTION_);

String[] arr3 = (String[])readInput("test3.txt", 3);

System.out.print("Test 3: ");

displayTestResult(arr3, SELECTION_);

Integer[] arr4 = (Integer[])readInput("test4.txt", 1);

System.out.print("Test 4: ");

displayTestResult(arr4, SELECTION_);

Integer[] arr5 = (Integer[])readInput("test5.txt", 1);

System.out.print("Test 5: ");

displayTestResult(arr5, SELECTION_);

}

catch (Exception e)

{

System.out.println("selectionSortTest: " + e.getMessage());

}

}

// automated test method for Insertion Sort

private static void insertionSortTest(){

try

{

System.out.println(" INSERTION SORT --------------");

Integer[] arr1 = (Integer[])readInput("test1.txt", 1);

System.out.print("Test 1: ");

displayTestResult(arr1, INSERTION_);

Double[] arr2 = (Double[])readInput("test2.txt", 2);

System.out.print("Test 2: ");

displayTestResult(arr2, INSERTION_);

String[] arr3 = (String[])readInput("test3.txt", 3);

System.out.print("Test 3: ");

displayTestResult(arr3, INSERTION_);

Integer[] arr4 = (Integer[])readInput("test4.txt", 1);

System.out.print("Test 4: ");

displayTestResult(arr4, INSERTION_);

Integer[] arr5 = (Integer[])readInput("test5.txt", 1);

System.out.print("Test 5: ");

displayTestResult(arr5, INSERTION_);

}

catch (Exception e)

{

System.out.println("insertionSortTest: " + e.getMessage());

}

}

// automated test method for QuickSort

private static void quickSortTest(){

try

{

System.out.println(" QUICKSORT --------------");

Integer[] arr1 = (Integer[])readInput("test1.txt", 1);

System.out.print("Test 1: ");

displayTestResult(arr1, QUICK_);

Double[] arr2 = (Double[])readInput("test2.txt", 2);

System.out.print("Test 2: ");

displayTestResult(arr2, QUICK_);

String[] arr3 = (String[])readInput("test3.txt", 3);

System.out.print("Test 3: ");

displayTestResult(arr3, QUICK_);

Integer[] arr4 = (Integer[])readInput("test4.txt", 1);

System.out.print("Test 4: ");

displayTestResult(arr4, QUICK_);

Integer[] arr5 = (Integer[])readInput("test5.txt", 1);

System.out.print("Test 5: ");

displayTestResult(arr5, QUICK_);

}

catch (Exception e)

{

System.out.println("quickSortTest: " + e.getMessage());

}

}

//automated test method for Merge Sort

private static void mergeSortTest(){

try

{

System.out.println(" MERGE SORT --------------");

Integer[] arr1 = (Integer[])readInput("test1.txt", 1);

System.out.print("Test 1: ");

displayTestResult(arr1, MERGE_);

Double[] arr2 = (Double[])readInput("test2.txt", 2);

System.out.print("Test 2: ");

displayTestResult(arr2, MERGE_);

String[] arr3 = (String[])readInput("test3.txt", 3);

System.out.print("Test 3: ");

displayTestResult(arr3, MERGE_);

Integer[] arr4 = (Integer[])readInput("test4.txt", 1);

System.out.print("Test 4: ");

displayTestResult(arr4, MERGE_);

Integer[] arr5 = (Integer[])readInput("test5.txt", 1);

System.out.print("Test 5: ");

displayTestResult(arr5, MERGE_);

}

catch (Exception e)

{

System.out.println("mergeSortTest: " + e.getMessage());

}

}

//automated test function for Shell Sort

private static void shellSortTest(){

try

{

System.out.println(" SHELL SORT --------------");

Integer[] arr1 = (Integer[])readInput("test1.txt", 1);

System.out.print("Test 1: ");

displayTestResult(arr1, SHELL_);

Double[] arr2 = (Double[])readInput("test2.txt", 2);

System.out.print("Test 2: ");

displayTestResult(arr2, SHELL_);

String[] arr3 = (String[])readInput("test3.txt", 3);

System.out.print("Test 3: ");

displayTestResult(arr3, SHELL_);

Integer[] arr4 = (Integer[])readInput("test4.txt", 1);

System.out.print("Test 4: ");

displayTestResult(arr4, SHELL_);

Integer[] arr5 = (Integer[])readInput("test5.txt", 1);

System.out.print("Test 5: ");

displayTestResult(arr5, SHELL_);

}

catch (Exception e)

{

System.out.println("shellSortTest: " + e.getMessage());

}

}

private static void displayTestResult(Comparable[] arr, int sort){

Comparable[] arrcopy = new Comparable[arr.length];

for (int i = 0; i

arrcopy[i] = arr[i];

System.out.print("n = " + arr.length);

System.out.print("\t barometer operations = ");

if (sort == SELECTION_)

System.out.print(A3Sorter.selectionSort(arr));

else if (sort == INSERTION_)

System.out.print(A3Sorter.insertionSort(arr));

else if (sort == QUICK_)

System.out.print(A3Sorter.quickSort(arr));

else if (sort == MERGE_)

System.out.print(A3Sorter.mergeSort(arr));

else if (sort == SHELL_)

System.out.print(A3Sorter.shellSort(arr));

System.out.print("\t contains all = " + contains(arrcopy, arr));

System.out.println("\t isSorted = " + isSorted(arr));

}

// Types - 1: Integer, 2: Double, 3: String

private static Comparable[] readInput(String inputFileName, int type){

switch(type){

case 1: // file contains Integers

ArrayList arrayListInt = new ArrayList();

try

{

File file = new File(inputFileName);

Scanner inputFile = new Scanner(file);

while (inputFile.hasNext())

arrayListInt.add(inputFile.nextInt());

inputFile.close();

return arrayListInt.toArray(new Integer[0]);

}

catch (IOException e)

{

System.out.println("readInput: " + e.getMessage());

}

break;

case 2: // file contains Doubles

ArrayList arrayListDouble = new ArrayList();

try

{

File file = new File(inputFileName);

Scanner inputFile = new Scanner(file);

while (inputFile.hasNext())

arrayListDouble.add(inputFile.nextDouble());

inputFile.close();

return arrayListDouble.toArray(new Double[0]);

}

catch (IOException e)

{

System.out.println("readInput: " + e.getMessage());

}

break;

case 3: // file contains Strings

ArrayList arrayListString = new ArrayList();

try

{

File file = new File(inputFileName);

Scanner inputFile = new Scanner(file);

while (inputFile.hasNext())

arrayListString.add(inputFile.nextLine());

inputFile.close();

return arrayListString.toArray(new String[0]);

}

catch (IOException e)

{

System.out.println("readInput: " + e.getMessage());

}

break;

}

return null; // should not encounter this statement

}

}

--------------------------------------------------------------------------------------------------

// File: A3Sorter.java

// Author: Geoffrey Tien/ Rita Ester

// (your name here)

// Date: 2017-10-06

// Description: Class contains static implementations of various

// array sorting algorithms.

public class A3Sorter {

// no public or private member attributes needed.

// you may declare your own private helper methods here

// all static sorting methods

// As example: implementation of SelectionSort

// Returns the number of barometer operations performed

public static int selectionSort(Comparable[] arr)

{

int count = 0; // for counting the barometer operation

for (int i = 0; i

int minIndex = i;

for (int j = i + 1; j

count++; // counts the barometer operation: the comparison of the for loop.

if (arr[j].compareTo(arr[minIndex])

minIndex = j;

}

count++; // counts the the barometer operation: the comparison of the for loop that results in false.

//exchange two array elements

Comparable> min = arr[minIndex];

arr[minIndex] = arr[i];

arr[i] = min;

}

return count;

}

// Implementation of Insertion Sort

// Returns the number of barometer operations performed

public static int insertionSort(Comparable[] arr)

{

int count = 0;

// your code

return count;

}

// Implementation of QuickSort

// Returns the number of barometer operations performed

public static int quickSort(Comparable[] arr)

{

return quickSort(arr, 0, arr.length-1);

}

// Recursive QuickSort

private static int quickSort(Comparable[] arr, int start, int end)

{

int count = 0;

// your code

return count;

}

// QuickSort partition

// Returns a 2-element int array. [0] contains the pivot index, [1] contains the barometer count.

private static int[] partition(Comparable[] arr, int start, int end)

{

int[] resultArray = new int[2]; // for holding results

int count = 0;

int pivotIndex=0;

// your code

resultArray[1] = pivotIndex;

resultArray[0]= count;

return resultArray;

}

// Implementation of MergeSort

// Returns the number of barometer operations performed

public static int mergeSort(Comparable[] arr)

{

return mergeSort(arr, 0, arr.length-1);

}

// Recursive MergeSort

private static int mergeSort(Comparable[] arr, int start, int end)

{

int count = 0;

// your code

return count;

}

// MergeSort's merge operation

// Returns barometer count

private static int merge(Comparable[] arr, int low, int middle, int high)

{

int count = 0;

// your code

return count;

}

// Implementation of Shell sort

// Cite your references here

// Requirements: Initial gap size n/2, reduce by 1/2 each iteration

public static int shellSort(Comparable[] arr)

{

int count = 0;

// your code

return count;

}

}

-------------------------------------------------------------------------------------------------------------

text1:

100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

-------------------------------------------------------------------------------------------------------

text 2:

86.74745842 83.71521534 68.25501728 96.4194838 41.86550704 86.70599347 8.688628153 99.91784013 54.5236355 43.33376956 32.85106826 9.776363098 70.08233263 17.74917368 83.49923593 10.20992608 84.82763519 91.51774282 39.89540031 13.02713223 32.59367169 94.13657226 68.21130593 5.279175839 7.532090879 19.77100452 29.5731304 51.0492019 25.41824588 46.21383959 75.70203536 33.11154896 56.49530727 97.0129956 47.3711966 93.72925682 93.52831481 24.24751698 10.12726448 48.74519398 89.50515954 46.58122237 64.81635394 82.78230044 85.21190029 7.017072728 2.664324395 50.26378967 57.21841674 61.49304557 12.67020263 93.235113 42.86588976 33.53052839 79.9830775 36.70704305 69.68640503 59.53280074 94.15797661 50.66164947 69.89447461 59.32273359 2.129506863 75.0929689 48.93751315 58.44596348 16.35963804 68.67374606 50.06269535 22.6761332 9.561570612 56.94505888 81.97970624 29.15165765 84.87282843 63.81294187 41.714426 17.04452101 37.12677907 78.39713805 38.98441617 0.61731646 84.66488484 80.07874706 86.52956693 99.2231809 24.09106111 41.27041502 81.8664985 33.29901458 87.59551692 83.20012658 21.0261342 49.11812444 41.66277543 42.57708565 92.00568493 70.83925949 86.91177401 21.41572948

------------------------------------------------------------------------------------------

text 3:

alpaca zebu platypus elephant doe capybara seal koodoo aoudad guanaco lynx squirrel quagga wolf orangutan jackal canary leopard cony gnu muskrat buffalo kitten llama lemur cat ape rabbit civet fawn reindeer vicuna stallion marten ewe waterbuck lizard badger kid gopher hog mole wildcat sheep lamb otter dromedary hamster horse goat pronghorn rat ibex frog salamander finch raccoon crow snake armadillo wolverine turtle bighorn hartebeest fish jaguar toad kinkajou newt hyena porpoise hedgehog reptile marmoset parakeet puppy fox addax ox coyote panda dingo mare opossum baboon cougar ferret giraffe basilisk mandrill chipmunk beaver bat gazelle bull whale hippopotamus elk alligator eland

-----------------------------------------------------------------------------------------

text 4:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

------------------------------------------------------------------------------------

text 5:

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

In this assignment, you are to implement different sorting algorithms. Please note the following: Your sorting methods operate on arrays of Comparable arrays, i.e use Comparable as the type of your array. The typecasts from Comparable to Integer, Double, and String are handled in A3Driver.java. You must use the compareTo() method to compare values. * Each sorting method should return an integer equal to the number of barometer operations performed during execution of the method; the barometer instruction is the (single) instruction or comparison that is executed the most number of times The skeleton A3Sorter.java file includes the stubs (empty methods, just returning 0) of all the sorting methods; these need to be completed for this assignment. Do not change the method headers! You may add your own private methods if needed. Part 1 - Insertion Sort public static int insertionSort (Comparable[] arr) Complete the implementation of Insertion Sort that sorts its array parameter using the insertion sort algorithm. The method should return an integer that equals the number of times its barometer comparison is performed during its execution. Part 2 - Quicksort public static int quickSort(Comparable[] arr) Complete the recursive method quickSort (Comparable[] arr, int start, int end) for sorting an array using the quick sort algorithm. This method hould return an integer that equals the number of times its barometer comparison is performed during its execution the partition method. The partition method returns an integer array; index 0 contains the pivot index, and indexl contains the number of times its barometer operation is executed. Note that as in the textbook, the partition method should first perform a swap of the element at the median array index with the element at the first array index, and then use the (new) first index as the pivot value (Note: The code of the partition method can also be directly integrated in the quicksort method. This makes it easier to count the barometer operations, and to determine the pivot element.)