The purpose of this problem is to design experiments to determine what algorithm 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 quicksort. Instead of going by these names, the methods are called sort(i,), for i= 0,1,2,3, (in no particular order). If you create an array A of Integer (or other type) and create objects of type MysterySorts, then s.sort(i, A) will sort A into increasing order, which is between 0 and 3, inclusive. There is also a method shuffleArray(which arranges A into a random order.Write a program called SortIdentifier that will identify which algorithm is used for sort(i,), 0?i?3. 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 quicksort, 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.

// 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 < A.length - 1; i++) { // Select i'th record

int lowindex = i; // Remember its index

for (int j = A.length - 1; j > i; j--)

// Find the least value

if (A[j].compareTo(A[lowindex]) < 0)

lowindex = j; // Put it in place

swap(A, i, lowindex);

}

}

> void hqsort(E[] A, int i, int j) { // Quicksort

if (j - i < 10)

return;

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

}

> 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)

;

while ((r != 0) && (A[--r].compareTo(pivot) >= 0))

;

swap(A, l, r); // Swap out-of-place values

} while (l < r); // Stop when they cross

swap(A, l, r); // Reverse last, wasted swap

return l; // Return first position in right partition

}

> 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; i++)

// Copy subarray to temp

temp[i] = A[i];

// Do the merge operation back to A

int i1 = l;

int i2 = mid + 1;

for (int curr = l; curr <= r; curr++) {

if (i1 == mid + 1) // Left sublist exhausted

A[curr] = temp[i2++];

else if (i2 > r) // Right sublist exhausted

A[curr] = temp[i1++];

else if (temp[i1].compareTo(temp[i2]) < 0) // Get smaller

A[curr] = temp[i1++];

else

A[curr] = temp[i2++];

}

}

> void inssort(E[] A) {

//System.out.println("inssort");

for (int i = 1; i < A.length; i++)

// Insert i'th record

for (int j = i; (j > 0) && (A[j].compareTo(A[j - 1]) < 0); j--)

swap(A, j, 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 < A.length; i++)

pq.add(A[i]);

for (int i = 0; i < A.length; i++)

// Now sort

A[A.length - i - 1] = pq.poll(); // Removemax places max at end

// of heap

}

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;

}

}

}

// 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 < A.length - 1; i++) { // Select i'th record int lowindex = i; // Remember its index for (int j = A.length - 1; j > i; j--) // Find the least value if (A[j].compareTo(A[lowindex]) < 0) lowindex = j; // Put it in place swap(A, i, lowindex); } }

/* Hybrid quicksort; halts recursion when array is small. */ > void hqsort(E[] A, int i, int j) { // Quicksort if (j - i < 10) return; 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 }

> 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) ; while ((r != 0) && (A[--r].compareTo(pivot) >= 0)) ; swap(A, l, r); // Swap out-of-place values } while (l < r); // Stop when they cross swap(A, l, r); // Reverse last, wasted swap return l; // Return first position in right partition }

> 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; i++) // Copy subarray to temp temp[i] = A[i]; // Do the merge operation back to A int i1 = l; int i2 = mid + 1; for (int curr = l; curr <= r; curr++) { if (i1 == mid + 1) // Left sublist exhausted A[curr] = temp[i2++]; else if (i2 > r) // Right sublist exhausted A[curr] = temp[i1++]; else if (temp[i1].compareTo(temp[i2]) < 0) // Get smaller A[curr] = temp[i1++]; else A[curr] = temp[i2++]; } }

> void inssort(E[] A) { for (int i = 1; i < A.length; i++) // Insert i'th record for (int j = i; (j > 0) && (A[j].compareTo(A[j - 1]) < 0); j--) swap(A, j, 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 < A.length; i++) pq.add(A[i]); for (int i = 0; i < A.length; i++) // Now sort A[A.length - i - 1] = pq.poll(); // Removemax (Java calls it poll. }

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; } } }