The purpose of this problem is to design experiments to determine what algorithm
ID: 3741641 • Letter: T
Question
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;
}
}
}
Explanation / Answer
ANS:-
PROGRAM:-
public class Sort {
public static void sort(int i, int arr[]){
if(i==0){
int[] a=insertionSort(arr);
System.out.println("After Insertion Sort array");
printArray(a);
}
else if(i==1){
int[] a=quickSort(arr,0,arr.length-1);
System.out.println("After Quick Sort array");
printArray(a);
}
else if(i==2){
int[] a=heapSort(arr);
System.out.println("After Heap Sort array");
printArray(a);
}
else if(i==3){
int[] a=selectionSort(arr);
System.out.println("After Selection Sort array");
printArray(a);
}
else{
System.out.println("Wrong selection: please check ");
}
}
public static int[] insertionSort(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
return arr;
}
public static int partition(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;
}
public static int[] quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
return arr;
}
public static int[] heapSort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
return arr;
}
public static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static int[] selectionSort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
return arr;
}
public static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
// 2 program
import java.util.Arrays;
import java.util.Scanner;
public class MysterySorts {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("please enter array elements:");
String str=sc.nextLine();
String[] sarray=str.split(" ");
int[] intArray=new int[sarray.length];
for(int i=0;i<intArray.length;i++){
intArray[i]=Integer.parseInt(sarray[i]);
}
System.out.println(Arrays.toString(intArray));
for(int i=0;i<=3;i++){
Sort.sort(i,intArray);
}
}
}
/*
output:-
please enter array elements:
3 1 5 2 9 6
[3, 1, 5, 2, 9, 6]
After Insertion Sort array
1 2 3 5 6 9
After Quick Sort array
1 2 3 5 6 9
After Heap Sort array
1 2 3 5 6 9
After Selection Sort array
1 2 3 5 6 9
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.