SOLVE IN JAVA!!!

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,.), for 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,-), 0