1. Create an Evaluator class that will evaluate the sorting algorithms. Create 1
ID: 3816101 • Letter: 1
Question
1. Create an Evaluator class that will evaluate the sorting algorithms. Create 1 method for each of the sorting algorithms below. Each method must accept 1 int[]as a parameter.
Selection sort
Insertion sort
Merge sort
Implement the code for each of the sort methods above by referring to Figures 19.6
// Fig. 19.6: SelectionSortTest.java
// Sorting an array with selection sort.
import java.security.SecureRandom;
import java.util.Arrays;
public class SelectionSortTest
{
// sort array using selection sort
public static void selectionSort(int[] data)
{
// loop over data.length - 1 elements
for (int i = 0; i < data.length - 1; i++)
{
int smallest = i; // first index of remaining array
// loop to find index of smallest element
for (int index = i + 1; index < data.length; index++)
if (data[index] < data[smallest])
smallest = index;
swap(data, i, smallest); // swap smallest element into position
printPass(data, i + 1, smallest); // output pass of algorithm
}
} // end method selectionSort
// helper method to swap values in two elements
private static void swap(int[] data, int first, int second)
{
int temporary = data[first]; // store first in temporary
data[first] = data[second]; // replace first with second
data[second] = temporary; // put temporary in second
}
// print a pass of the algorithm
private static void printPass(int[] data, int pass, int index)
{
System.out.printf("after pass %2d: ", pass);
// output elements till selected item
for (int i = 0; i < index; i++)
System.out.printf("%d ", data[i]);
System.out.printf("%d* ", data[index]); // indicate swap
// finish outputting array
for (int i = index + 1; i < data.length; i++)
System.out.printf("%d ", data[i]);
System.out.printf("%n "); // for alignment
// indicate amount of array that’s sorted
for (int j = 0; j < pass; j++)
System.out.print("-- ");
System.out.println();
}
public static void main(String[] args)
{
SecureRandom generator = new SecureRandom();
int[] data = new int[10]; // create array
for (int i = 0; i < data.length; i++) // populate array
data[i] = 10 + generator.nextInt(90);
System.out.printf("Unsorted array:%n%s%n%n",
Arrays.toString(data)); // display array
selectionSort(data); // sort array
System.out.printf("Sorted array:%n%s%n%n",
Arrays.toString(data)); // display array
}
} // end class SelectionSortTest
2. Exclude any portions of the textbook code that print anything to the output window. The goal here is to evaluate the efficiency of the sort algorithms, not how quickly they can print things to the console.
3. Add 3 further methods to the Evaluator class that perform the following tasks:
Returns an array with 100,000 int values in sequential order, starting with 1 and ending with 100,000.
Returns an array with 100,000 random int values.
Returns an array with 100,000 int values in descending sequential order, starting with 100,000 and ending with 1.
4. In the main method:Use the Evaluator class to evaluate each sorting algorithm with each of the 3 arrays (best, average, and worst case) for a total of 9 distinct tests.
Store the result of System.nanoTime() before and after each call to the sorting method, and calculate the time in nano-seconds it takes to complete each test (i.e., subtract the time taken before the test from the time taken after the test).
Generate new arrays prior to each test, but do not include the generation of the arrays in the evaluation of sort time.
5. Output a table showing the best, average, and worst case times for each of the sorting algorithms
Explanation / Answer
Code
import java.util.Random;
public class Evaluator {
public static final int size =5;
public static void main(String[] args) {
System.out.println("Sorting Algorithm BestCase Average WorstCase");
System.out.println("__________________________________________________________________");
//insertionsort
int[] a = sequential();
long start = System.nanoTime();
insertionSort(a);
long end = System.nanoTime();
System.out.print("InsertionSort ");
System.out.print(end-start+" ");
a = random();
start = System.nanoTime();
insertionSort(a);
end = System.nanoTime();
System.out.print(end-start+" ");
a = decresing();
start = System.nanoTime();
insertionSort(a);
end = System.nanoTime();
System.out.println(end-start+" ");
System.out.println();
//selectionsort
a = sequential();
start = System.nanoTime();
selection(a);
end = System.nanoTime();
System.out.print("SelectionSort ");
System.out.print(end-start+" ");
a = random();
start = System.nanoTime();
selection(a);
end = System.nanoTime();
System.out.print(end-start+" ");
a = decresing();
start = System.nanoTime();
selection(a);
end = System.nanoTime();
System.out.println(end-start+" ");
System.out.println();
//mergesort
a = sequential();
start = System.nanoTime();
mergesort(a,0,size-1);
end = System.nanoTime();
System.out.print("MergeSort ");
System.out.print(end-start+" ");
a = random();
start = System.nanoTime();
mergesort(a,0,size-1);
end = System.nanoTime();
System.out.print(end-start+" ");
a = decresing();
start = System.nanoTime();
mergesort(a,0,size-1);
end = System.nanoTime();
System.out.println(end-start+" ");
System.out.println();
}
public static void print(int a[]) {
System.out.println("Printing the array");
for (int j = 0; j <= a.length - 1; j++) {
System.out.print(a[j] + " ");
}
System.out.println();
}
public static int[] sequential() {
int[] temp = new int[size];
for (int i = 0; i < size; i++)
temp[i] = i + 1;
return temp;
}
public static int[] random() {
int[] temp = new int[size];
Random r = new Random();
for (int i = 0; i < size; i++)
temp[i] = r.nextInt(size) + 1;
return temp;
}
public static int[] decresing() {
int[] temp = new int[size];
for (int i = 0; i < size; i++)
temp[i] = size - i;
return temp;
}
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
public static int[] selection(int a[]) {
int[] b = a;
for (int i = 0; i < b.length - 1; i++) {
int min_index = i;
for (int j = i + 1; j <= b.length - 1; j++)
if (b[j] < b[min_index])
min_index = j;
int temp = b[min_index];
b[min_index] = b[i];
b[i] = temp;
}
return b;
}
public static void mergesort(int a[], int l, int h) {
if (l < h) {
int m = (l + h) / 2;
mergesort(a, l, m);
mergesort(a, m + 1, h);
merge(a, l, m, h);
}
}
public static void merge(int a[], int l, int m, int h) {
int n1 = m - l + 1, n2 = h - m;
int[] L = new int[n1], R = new int[n2];
int i, j, k;
for (i = 0; i < n1; i++)
L[i] = a[l + i];
for (i = 0; i < n2; i++)
R[i] = a[m + 1 + i];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
a[k] = L[i];
i++;
k++;
}
while (j < n2) {
a[k] = R[j];
j++;
k++;
}
}
}
Sampleoutput
Sorting Algorithm BestCase Average WorstCase
__________________________________________________________________
InsertionSort 1983 1207 732
SelectionSort 2806 1003 944
MergeSort 7322 4251 2816
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.