Help on (d.)/(e.)/(f.) Create a class called InsertionSort that implements SortA
ID: 3847725 • Letter: H
Question
Help on (d.)/(e.)/(f.)
Create a class called InsertionSort that implements SortAnalysis in a file named InsertionSort.java and use it to do the following:
a) Describe a way of arranging elements of an array of length n such that the running time would be a worst-case for your InsertionSort algorithm.
b) Write a program to determine the size n of the array that gives a running time of 1000 milliseconds. (Similar to (a) in Part 1.)
c) Create a worst-case array as described in (a) for 50 ”equally spaced sizes” between 1 and the size determined in part (b); and compute the running time of your algorithm on these arrays.
d) Plot the results of (b) on a graph alongside a plot of the analytical well-known worst-case running time of insertion sort and a best fit polynomial curve of degree 2.
e) Create a pdf file that shows the plots from (d) and explain the differences you see in these plots.
f) Repeat (b) through (e) except use random data for your analysis instead of worst-case data. Be sure to also explain in the pdf reasons for differences between worse case data and random data.
Interfaces Implemented
import java.util.ArrayList;
public interface sortAnalysis<E extends Comparable<? super E>> {
/**
* Sorts the list of elements and returns the amount of time required to sort them. (in milliseconds)
* @param list
* A list of comparable elements to be sorted and analyzed.
* @return list The time required to sort the list.
*/
public long analyzeSort(ArrayList<E> list);
}
public interface MatrixAnalysis {
/**
* @param double[][] m1 The first square matrix to multiply
* @param double[][] m2 The second square matrix to multiply
* @param double[][] m3 The result is placed in the square matrix m3 = m1 *
* @return long The time in the number of milliseconds for the mutiple to complete
*
*/
public long analyzeMultiply(double [][] m1, double[][] m2, double [][] m3);
/**
* @param double[][] m1 The square matrix to take the inverse of
*
* @param double[][] m2 The resultant inverse
*
* @return long The time in the number of milliseconds for the multiple to complete
*
*/
public long analyzeInverse(double [][] m1, double[][] m2);
}
CODE:
======================================================
//InsertionSort.java
import java.util.ArrayList;
import java.util.Random;
public class InsertionSort implements SortAnalysis<Integer> {
@Override
public long analyzeSort(ArrayList<Integer> list) {
long startTime = System.currentTimeMillis();
for(int i = 1; i < list.size(); i++) {
int k = i;
while(k > 0 && list.get(k) < list.get(k-1)) {
int temp = list.get(k);
list.set(k, list.get(k-1));
list.set(k-1, temp);
k--;
}
}
return System.currentTimeMillis()-startTime;
}
public ArrayList<Integer> createFilledArray(boolean random, int size) {
ArrayList<Integer> array = new ArrayList<Integer>();
if(random == true) {
Random getRandom = new Random();
for(int i = 0; i < size; i++) {
array.add(getRandom.nextInt());
}
}
else {
for(int i = size; i > 0; i--) {
array.add(i);
}
}
return array;
}
public int binarySearch(int min, int max, boolean randomElements) {
ArrayList<Integer> array;
int mid = ((min+max)/2);
if(randomElements == false) {
array = createFilledArray(false, mid);
}
else {
array = createFilledArray(true, mid);
}
long time = analyzeSort(array);
if(time == 1000) {
return mid;
}
if (time > 1000) {
array = createFilledArray(false, mid-1);
time = analyzeSort(array);
if(time <= 1000) {
return mid;
}
else {
if(randomElements == true) {
return binarySearch(min, mid-1, true);
}
else {
return binarySearch(min, mid-1, false);
}
}
}
else {
array = createFilledArray(false, mid+1);
time = analyzeSort(array);
if(time >= 1000) {
return mid+1;
}
else {
if(randomElements == true) {
return binarySearch(mid+1, max, true);
}
else {
return binarySearch(mid+1, max, false);
}
}
}
}
public static void main(String[] args) {
long timeTaken = 0;
int size = 1;
InsertionSort insertionSort = new InsertionSort();
//Worst Case Data
while(timeTaken < 1000) {
ArrayList<Integer> array = insertionSort.createFilledArray(false, size);
timeTaken = insertionSort.analyzeSort(array);
size *= 2;
}
int finalSize = insertionSort.binarySearch(size/4, size/2, false);
System.out.println("Size to be over 1000 ms: " + finalSize);
int step = finalSize/100;
for(int i = 1; i <= 100; i++) {
ArrayList<Integer> worstArray = insertionSort.createFilledArray(false, step*i);
long worstTimeTaken = insertionSort.analyzeSort(worstArray);
System.out.println(worstTimeTaken);
}
//End of Worst Case Data
//Random Data
while(timeTaken < 1000) {
ArrayList<Integer> array = insertionSort.createFilledArray(true, size);
timeTaken = insertionSort.analyzeSort(array);
size *= 2;
}
finalSize = insertionSort.binarySearch(size/4, size/2, true);
System.out.println("Size to be over 1000 ms: " + finalSize);
step = finalSize/100;
for(int i = 1; i <= 100; i++) {
ArrayList<Integer> worstArray = insertionSort.createFilledArray(true, step*i);
long worstTimeTaken = insertionSort.analyzeSort(worstArray);
System.out.println(worstTimeTaken);
}
//End of Random Data
}
}
=======================================================================
//SortAnalysis.java
import java.util.ArrayList;
public interface SortAnalysis<E extends Comparable<? super E>> {
public long analyzeSort(ArrayList<E> list);
}
Explanation / Answer
Public class insertion sort
{
Public static void insertionsort(int array[])
{
Int n=array.length
For(j=o; j<n ; j++)
{
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.