Interfaces Implemented import java.util.ArrayList; public interface sortAnalysis
ID: 3847629 • Letter: I
Question
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);
}
Create a class called MatrixOperations that implements MatrixAnalysis. Note that if you do not intend to do the bonus problem, you may throw a not implemented exception for the analyzelnverse method. For the analyze Multiply method, implement the multiply method using the standard O(na) algorithm you learned in school and use it to do the following. a) Write a main method that determines the first size of input number of rows in the array) required to make the algorithm run for at least 1000 milliseconds. To do this you must first start with an array of size of 1 and then double the size til you have a running time greater than 1000 milliseconds. The use a binary search to determine the exact size that is over 1000 miliseconds, but size-1 is under. All input should be a matrix filled with random data. b) rite a main method that outputs the times 20 "equally spaced sizes between 1 and the size determined in part a c Graph the result from part b and determine the best fit curve of poly nomial degree 3. Note that Excel contains an easy way to so this and nicely display the equation, but you may use other curve fitting pro- grams if you wish. Google "excel curve fitting" may give many good results for how to do this d) Provide a pdf document that shows the graph and equation from part c and discuss your results.Explanation / Answer
//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
}
}
=========================================================================
//MatrixAnalysis.java
public interface MatrixAnalysis {
public long analyzeMultiply(double[][] m1, double[][] m2, double[][] m3);
public long analyzeInverse(double[][] m1, double[][] m2);
}
==========================================================================
//MatrixOperations.java
import java.util.Random;
public class MatrixOperations implements MatrixAnalysis {
@Override
public long analyzeMultiply(double[][] m1, double[][] m2, double[][] m3) {
long startTime = System.currentTimeMillis();
for(int i = 0; i < m1.length; i++) {
for(int j = 0; j < m2[i].length; j++) {
for(int k = 0; k < m1[i].length; k++) {
m3[i][j] += m1[i][k]*m2[k][j];
}
}
}
long endTime = System.currentTimeMillis();
return endTime-startTime;
}
/**
* Not currently implemented
*/
@Override
public long analyzeInverse(double[][] m1, double[][] m2) {
// TODO Auto-generated method stub
return 0;
}
public static double[][] createFilledSquareMatrix(int size) {
double[][] matrix = new double[size][size];
Random random = new Random();
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
matrix[i][j] = random.nextDouble() * 3 + random.nextInt() * 3;
}
}
return matrix;
}
public int binarySearch(int min, int max) {
int mid = ((min+max)/2);
double[][] m1 = createFilledSquareMatrix(mid);
double[][] m2 = createFilledSquareMatrix(mid);
double[][] m3 = new double[mid][mid];
long time = analyzeMultiply(m1, m2, m3);
if(time == 1000) {
return mid;
}
if (time > 1000) {
m1 = createFilledSquareMatrix(mid-1);
m2 = createFilledSquareMatrix(mid-1);
m3 = new double[mid-1][mid-1];
time = analyzeMultiply(m1, m2, m3);
if(time <= 1000) {
return mid;
}
else {
return binarySearch(min, mid-1);
}
}
else {
m1 = createFilledSquareMatrix(mid+1);
m2 = createFilledSquareMatrix(mid+1);
m3 = new double[mid+1][mid+1];
time = analyzeMultiply(m1, m2, m3);
if(time >= 1000) {
return mid+1;
}
else {
return binarySearch(mid+1, max);
}
}
}
public static void main(String[] args) {
long timeTaken = 0;
int size = 1;
MatrixOperations matrix = new MatrixOperations();
while(timeTaken < 1000) {
double[][] m1 = createFilledSquareMatrix(size);
double[][] m2 = createFilledSquareMatrix(size);
double[][] m3 = new double[size][size];
timeTaken = matrix.analyzeMultiply(m1, m2, m3);
size *= 2;
}
int finalSize = matrix.binarySearch(size/4, size/2);
System.out.println("Size to be over 1000 ms: " + finalSize);
for(int i = 1; i <= finalSize; i++) {
double[][] m1 = createFilledSquareMatrix(i);
double[][] m2 = createFilledSquareMatrix(i);
double[][] m3 = new double[i][i];
long averageTime = 0;
for(int k = 0; k < 3; k++) {
averageTime += matrix.analyzeMultiply(m1, m2, m3);
}
averageTime /= 3;
System.out.println(averageTime);
}
}
}
===============================================================================
//QuickSort.java
import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;
public class QuickSort implements SortAnalysis<Integer> {
/**
* This boolean variable is used to indicate if the worst case is to be considered or not.
* Not using this variable would require additions to analyzeSort so I decided to use it instead
*/
private static boolean worstCase = true;
@Override
public long analyzeSort(ArrayList<Integer> list) {
long startTime = System.currentTimeMillis();
Stack<Integer> partitionBounds = new Stack<Integer>();
partitionBounds.push(list.size()-1);
partitionBounds.push(0);
if(list.size() == 0 || list.size() == 1) {
return System.currentTimeMillis()-startTime;
}
while(!partitionBounds.isEmpty()) {
int lowerBound = partitionBounds.pop();
int upperBound = partitionBounds.pop();
int bounds = partition(list, lowerBound, upperBound);
if(bounds-1 > lowerBound) {
partitionBounds.add(bounds-1);
partitionBounds.add(lowerBound);
}
if(bounds+1 < upperBound) {
partitionBounds.add(upperBound);
partitionBounds.add(bounds+1);
}
}
return System.currentTimeMillis()-startTime;
}
/**
* This function partitions our arraylist for quicksort and performs the swaps based on element conditions
*
* @param array The array to perform the partition on
* @param lowerBound Where to begin the partition
* @param upperBound Where to end the partition
* @return the "meeting point" of upper and lower bounds such that new partitions can be created
*/
public int partition(ArrayList<Integer> array, int lowerBound, int upperBound) {
int pivot;
if(worstCase == true) {
pivot = array.get(lowerBound);
}
else {
pivot = array.get((lowerBound+upperBound)/2);
}
while(true) {
if(array.get(lowerBound) == pivot && array.get(upperBound) == pivot) {
upperBound--;
}
while(array.get(lowerBound) < pivot) {
lowerBound++;
}
while(array.get(upperBound) > pivot) {
upperBound--;
}
if(lowerBound < upperBound) {
swapElements(array, lowerBound, upperBound);
}
else {
return lowerBound;
}
}
}
/**
* Helper function to swap to elements in an arraylist
* @param arrayToSwap the array we are swapping in
* @param pos1 the position of the first element to swap
* @param pos2 the position of the second element to swap
*
*/
public void swapElements(ArrayList<Integer> arrayToSwap, int pos1, int pos2) {
int temp = arrayToSwap.get(pos1);
arrayToSwap.set(pos1, arrayToSwap.get(pos2));
arrayToSwap.set(pos2, temp);
}
/**
* Function used to fill an array with either random elements or quicksort worst case elements
* @param random boolean indicating if random or quicksort worst case elements should be used.
* @param size the size of the array to create
* @return The created array
*/
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(1000));
}
}
else {
for(int i = 0; i < size; i++) {
array.add(i);
}
}
return array;
}
/**
* Binary search function to determine the exact running time over 1000 milliseconds of our quick sort
* @param min bottom value to search from
* @param max top value to search from
* @param randomElements determines if random elements should be used or worst case elements should be used
* @return the array size needed to produce a 1000 millisecond runtime
*/
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;
QuickSort quickSort = new QuickSort();
//Worst Case Data
while(timeTaken < 1000) {
ArrayList<Integer> array = quickSort.createFilledArray(false, size);
//System.out.println(array.toString());
timeTaken = quickSort.analyzeSort(array);
System.out.println(size + " " + timeTaken);
size *= 2;
}
int finalSize = quickSort.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 = quickSort.createFilledArray(false, step*i);
long worstTimeTaken = quickSort.analyzeSort(worstArray);
System.out.println(worstTimeTaken);
}
//End of Worst Case Data
//Start of Random Case Data
worstCase = false;
while(timeTaken < 1000) {
ArrayList<Integer> array = quickSort.createFilledArray(true, size);
//System.out.println(array.toString());
timeTaken = quickSort.analyzeSort(array);
System.out.println(size + " " + timeTaken);
size *= 2;
}
finalSize = quickSort.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 = quickSort.createFilledArray(true, step*i);
long worstTimeTaken = quickSort.analyzeSort(worstArray);
System.out.println(worstTimeTaken);
}
//End of Random Case Data
}
}
=======================================================================
//SortAnalysis.java
import java.util.ArrayList;
public interface SortAnalysis<E extends Comparable<? super E>> {
public long analyzeSort(ArrayList<E> list);
}
=======================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.