Given: MysterySorts.java import java.util.ArrayList; import java.util.Arrays; import java.util.Random; import java.util.PriorityQueue; /* * Implementations of various sorting algorithms. */ public class MysterySorts { > void sort(int i, E[] A) { switch(i) { case 0: selectsort(A); break; case 1: inssort(A); break; case 2: heapsort(A); break; case 3: quicksort(A); break; default: System.exit(7); break; } } > void sort5(E[] A) { E[] temp = A.clone(); mergesort(A, temp, 0, A.length-1); } > void selectsort(E[] A) { //System.out.println("selectsort"); for (int i = 0; i i; j--) // Find the least value if (A[j].compareTo(A[lowindex]) void hqsort(E[] A, int i, int j) { // Quicksort if (j - i 1) qsort(A, i, k - 1); // Sort left partition if ((j - k) > 1) qsort(A, k + 1, j); // Sort right partition } > void quicksort(E[] A) { // Quicksort qsort(A, 0, A.length - 1); } > void qsort(E[] A, int i, int j) { // Quicksort //System.out.println("qsort"); int pivotindex = findpivot(A, i, j); // Pick a pivot swap(A, pivotindex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i - 1, j, A[j]); swap(A, k, j); // Put pivot in place if ((k - i) > 1) qsort(A, i, k - 1); // Sort left partition if ((j - k) > 1) qsort(A, k + 1, j); // Sort right partition } > int findpivot(E[] A, int i, int j) { // return (i + j) / 2; return j; } > int partition(E[] A, int l, int r, E pivot) { do { // Move bounds inward until they meet while (A[++l].compareTo(pivot) = 0)) ; swap(A, l, r); // Swap out-of-place values } while (l void mergesort(E[] A, E[] temp, int l, int r) { int mid = (l + r) / 2; // Select midpoint if (l == r) return; // List has one element mergesort(A, temp, l, mid); // Mergesort first half mergesort(A, temp, mid + 1, r); // Mergesort second half for (int i = l; i r) // Right sublist exhausted A[curr] = temp[i1++]; else if (temp[i1].compareTo(temp[i2]) void inssort(E[] A) { //System.out.println("inssort"); for (int i = 1; i 0) && (A[j].compareTo(A[j - 1]) void heapsort(E[] A) { // The heap constructor invokes the buildheap method //System.out.println("heapsort"); // MaxHeap H = new MaxHeap(A); PriorityQueue pq = new PriorityQueue(A.length); for (int i = 0; i void swap(E[] A, int i, int j) { E temp = A[j]; A[j] = A[i]; A[i] = temp; } public static > void shuffleArray(E[] ar) { Random rnd = new Random(); for (int i = ar.length - 1; i > 0; i--) { int index = rnd.nextInt(i + 1); // Simple swap E a = ar[index]; ar[index] = ar[i]; ar[i] = a; } } }

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

Experiment.java

import java.util.ArrayList; import java.text.NumberFormat;

/* Program sorts many arrays using one of the "Mystery" sorts * sort1-sort4. You can plot the run times using Plot (if compatable * with where you are running the program) or simply print out the * results and plot with any plotting software. */

public class Experiment {

public static void main(String[] args) { MysterySorts srts = new MysterySorts(); int n; int k = 30; // experiment size int REP = 10; // how many times to repeat experiment

int[] data = new int[k]; // to store run times for (int i = 0; i

long start = System.currentTimeMillis(); for (int rep = 0; rep

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

Plot.java

import java.awt.*; import java.awt.geom.*; import javax.swing.*; public class Plot extends JPanel { int[] data; final int PAD = 20; Plot(int[] d){ data = d; } protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 = (Graphics2D)g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); int w = getWidth(); int h = getHeight(); // Draw ordinate. g2.draw(new Line2D.Double(PAD, PAD, PAD, h-PAD)); // Draw abcissa. g2.draw(new Line2D.Double(PAD, h-PAD, w-PAD, h-PAD)); double xInc = (double)(w - 2*PAD)/(data.length-1); double scale = (double)(h - 2*PAD)/getMax(); // Mark data points. g2.setPaint(Color.red); for(int i = 0; i max) max = data[i]; } return max; } public static void view(int[] data) { //int[] data = {2,3,6,9,35}; JFrame f = new JFrame(); f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); f.add(new Plot(data)); f.setSize(400,400); f.setLocation(200,200); f.setVisible(true); } }

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

Sorts.java

import java.util.ArrayList; import java.util.Arrays; import java.util.Random; import java.util.PriorityQueue;

/* * Implementations of various sorting algorithms we have covered. */

public class Sorts {

> void selectsort(E[] A) { for (int i = 0; i i; j--) // Find the least value if (A[j].compareTo(A[lowindex])

/* Hybrid quicksort; halts recursion when array is small. */ > void hqsort(E[] A, int i, int j) { // Quicksort if (j - i 1) qsort(A, i, k - 1); // Sort left partition if ((j - k) > 1) qsort(A, k + 1, j); // Sort right partition }

> void quicksort(E[] A) { // Quicksort qsort(A, 0, A.length - 1); }

> void qsort(E[] A, int i, int j) { // Quicksort int pivotindex = findpivot(A, i, j); // Pick a pivot swap(A, pivotindex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i - 1, j, A[j]); swap(A, k, j); // Put pivot in place if ((k - i) > 1) qsort(A, i, k - 1); // Sort left partition if ((j - k) > 1) qsort(A, k + 1, j); // Sort right partition }

> int findpivot(E[] A, int i, int j) { // return (i + j) / 2; return j; }

> int partition(E[] A, int l, int r, E pivot) { do { // Move bounds inward until they meet while (A[++l].compareTo(pivot) = 0)) ; swap(A, l, r); // Swap out-of-place values } while (l

> void mergesort(E[] A, E[] temp, int l, int r) { int mid = (l + r) / 2; // Select midpoint if (l == r) return; // List has one element mergesort(A, temp, l, mid); // Mergesort first half mergesort(A, temp, mid + 1, r); // Mergesort second half for (int i = l; i r) // Right sublist exhausted A[curr] = temp[i1++]; else if (temp[i1].compareTo(temp[i2])

> void inssort(E[] A) { for (int i = 1; i 0) && (A[j].compareTo(A[j - 1])

> void heapsort(E[] A) { // The heap constructor invokes the buildheap method // MaxHeap H = new MaxHeap(A); PriorityQueue pq = new PriorityQueue(A.length); for (int i = 0; i

private static > void swap(E[] A, int i, int j) { E temp = A[j]; A[j] = A[i]; A[i] = temp; }

public static > void shuffleArray(E[] ar) { Random rnd = new Random(); for (int i = ar.length - 1; i > 0; i--) { int index = rnd.nextInt(i + 1); // Simple swap E a = ar[index]; ar[index] = ar[i]; ar[i] = a; } } }

The purpose of this problem is to design experiments to determine what algo- rithm is used for a sorting method. In the "Sorting programs" directory on moodle you will find a file MysterySorts.java which contains methods implementing four sorting algorithms: insertion sort, selection sort, heap sort, and quick sort. In stead of going by these names, the methods are called sort(i, fori 0,1,2,3 (in no particular order). If you create an array A of Integer (or other comparable type) and create an object s of type MysterySorts, then s.sort(i,A) will sort A into increasing order, where i is between 0 and 3, inclusive. There is also a method shuffleArray(A) which arranges A into random order Write a program called SortIdentifier that will identify which algorithm is used for sort(i), 0i3. You may assume that there is a MysterySorts.java file in the same directory as your program. Your program takes no input. The output is four lines, with the sorting algorithm corresponding to sort (0, ) through sort (3, For example, if your program determines that sort(0, is insertion sort, sort (1,) is quick sort, sort(2, ) is heap sort, and sort(3, ) is selection sort, then the correct output is: insertion quick heap selection The only valid outputs are the 4! 24 different orderings of the four words. The class Sorts.java contains the implementations of the sorting algorithms. Note that the version of quicksort uses the right-most array element as the pivot. The purpose of this problem is to design experiments to determine what algo- rithm is used for a sorting method. In the "Sorting programs" directory on moodle you will find a file MysterySorts.java which contains methods implementing four sorting algorithms: insertion sort, selection sort, heap sort, and quick sort. In stead of going by these names, the methods are called sort(i, fori 0,1,2,3 (in no particular order). If you create an array A of Integer (or other comparable type) and create an object s of type MysterySorts, then s.sort(i,A) will sort A into increasing order, where i is between 0 and 3, inclusive. There is also a method shuffleArray(A) which arranges A into random order Write a program called SortIdentifier that will identify which algorithm is used for sort(i), 0i3. You may assume that there is a MysterySorts.java file in the same directory as your program. Your program takes no input. The output is four lines, with the sorting algorithm corresponding to sort (0, ) through sort (3, For example, if your program determines that sort(0, is insertion sort, sort (1,) is quick sort, sort(2, ) is heap sort, and sort(3, ) is selection sort, then the correct output is: insertion quick heap selection The only valid outputs are the 4! 24 different orderings of the four words. The class Sorts.java contains the implementations of the sorting algorithms. Note that the version of quicksort uses the right-most array element as the pivot