Hello, this is for Java. Any help would be amazing. Implement a program (command
ID: 3705085 • Letter: H
Question
Hello, this is for Java. Any help would be amazing.
Implement a program (command-line one will do) that generates two double arrays of length n, filled with identical random doubles between 0 and 1. Sort one array using bubble sort, and the other using merge sort (both of which you must implement). Time each execution and print the result. If it takes longer than 20 seconds, stop executing and report the fact. If you run out of memory, stop executing and report the fact. Exception handling will help here – don’t let your program crash or run for hours.
Your program should do this over and over until you either run out of memory or neither sort finishes within twenty seconds. Start n out at ten, and multiply by 10 each time, so you’re testing the algorithm at n = 10, 100, 1000, 10000, etc. Write a couple of lines in the code’s comments discussing the running time difference between O(n^2 ) and O(n log n) sorting methods.
Explanation / Answer
package solution.sorttime;
import java.util.Arrays;
public class ArraySortTestDriver {
public static void main(String[] args) {
int n = 10;
boolean bubbleFail = false;
boolean mergeFail = false;
do {
// create two array
double[] firstArray = SortUtil.getArrayOfDouble(n);
if (firstArray != null && firstArray.length > 0) {
double[] secondArray = new double[n];
secondArray = Arrays.copyOf(firstArray, firstArray.length);
// apply sort function over two array and trap the exception if occur.
try {
SortUtil.bubbleSort(secondArray);
}catch(RuntimeException runTimeExec){
bubbleFail=true;
System.out.println(runTimeExec.getMessage());
}
catch (OutOfMemoryError E) {
bubbleFail=true;
System.out.println("OutOfMemoryError occurred in Bubble Sort for Array Length ="+n);
}
try {
SortUtil.doMergeSort(firstArray);
}catch(RuntimeException runTimeExec){
System.out.println(runTimeExec.getMessage());
mergeFail=true;
}
catch (OutOfMemoryError E) {
System.out.println("OutOfMemoryError occurred in Merge Sort for Array Length ="+n);
mergeFail=true;
}
if(mergeFail && bubbleFail){
break;
}
}
System.out.println("********** next iteration********");
n = n * 10;
} while (n !=-1);
System.out.println("********** Execution stopped at arrayLength= "+n);
}
}
/////////////////////////////////////////////// array creation and sort util class /////////////////////////
package solution.sorttime;
import java.util.Date;
import java.util.Random;
import com.sun.jmx.snmp.Timestamp;
public class SortUtil {
// ////////////////MERGE SORT HELPER FUNCTION///////////////////////////
public static void doMergeSort(double[] sourceArray) {
Timestamp timestamp = new Timestamp(System.currentTimeMillis());
// display time and date using toString()
System.out.println("Merge sort starts at=>" + timestamp);
long startTime = System.currentTimeMillis();
mergeSortImpl(sourceArray,startTime);
Timestamp endTimestamp = new Timestamp(System.currentTimeMillis());
// display time and date using toString()
System.out.println("Merge sort Ends at=>" + endTimestamp);
}
public static void mergeSortImpl(double[] sourceArray, long startTime) {
final long start =startTime;
long now = System.currentTimeMillis();
if ((now - start) / 1000.0 > 20) {
// Report fact and break the loop
System.out
.println("Merge Sort Execution taking more than 20 seconds, thus suspending------");
throw new RuntimeException("Execution time elapsed in Merge Sort!!!");
}
int size = sourceArray.length;
if (size < 2)
return;
int mid = size / 2;
int leftSize = mid;
int rightSize = size - mid;
double[] left = new double[leftSize];
double[] right = new double[rightSize];
for (int i = 0; i < mid; i++) {
left[i] = sourceArray[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = sourceArray[i];
}
mergeSortImpl(left,startTime);
mergeSortImpl(right,startTime);
merge(left, right, sourceArray);
}
public static void merge(double[] left, double[] right, double[] argArray) {
int leftSize = left.length;
int rightSize = right.length;
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
argArray[k] = left[i];
i++;
k++;
} else {
argArray[k] = right[j];
k++;
j++;
}
}
while (i < leftSize) {
argArray[k] = left[i];
k++;
i++;
}
while (j < leftSize) {
argArray[k] = right[j];
k++;
j++;
}
}
// //////////////// BUBBLE SORT HELPER FUNCTION///////////////////////////
static void bubbleSort(double[] arr) throws RuntimeException {
int n = arr.length;
long startTime = System.currentTimeMillis();
// display time and date using toString()
System.out.println("Bubble sort starts at=>" + new Date().toString());
double temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (arr[j - 1] > arr[j]) {
// swap elements
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
long now = System.currentTimeMillis();
if ((now - startTime) / 1000.0 > 20) {
// Report fact and break the loop
System.out
.println("Bubble Sort Execution taking more than 20 seconds, thus suspending------");
throw new RuntimeException("Execution time elapsed in Bubble Sort!!!");
}
}
}
Date endTime = new Date();
// display time and date using toString()
System.out.println("Bubble sort Ends at =>" + endTime.toString());
}
// /////////////////// Array Creation with random double////////////
public static double[] getArrayOfDouble(int length) {
double[] anArray = null;
if (length > 0) {
anArray = new double[length];
Random rand = new Random();
for (int i = 0; i < anArray.length; i++) {
double randomNum = rand.nextDouble();
anArray[i] = randomNum;
}
}
return anArray;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.