A java class is provided below named JavaTimer.java with standard code for four kinds of sort: insertionSort, selectionSort, mergeSort, and quickSort. Expand the main() method to do the following: Create the following arrays of random integers: Array a b C d e Number of random integers 100 1000 O 10,000 100,000 1,000,000 Use the following code to measure the time a given sort needs to sort the array. randomizeArray(a); long startTime = System.nanoTime(); sortArray(a); long endTime = System.nanoTime(); long duration = (endTime - startTime) / 10001; Measure the time it takes for: insertionSort, selectionSort, mergeSort, and quickSort each to sort the arrays. Your arrays will be sorted after you call the sort routines! Make sure to reinitialize the arrays with random values before each sort. Output the time it takes for the sorts to run on each of the arrays. You will have to increase the size of the console pane to capture all the output. Our program output could look like the listing on the right. Our running times will probably be different than these. Testing an array of length 100. Quick sort: 23ms Merge sort: 67ms Insertion sort: 71ms Selection sort: 107ms Testing an array of length 1000. Quick sort: 339ms Merge sort: 429ms Insertion sort: 1790ms Selection sort: 2354ms Testing an array of length 10000. Quick sort: 1131ms Merge sort: 1154ms Insertion sort: 37014ms Selection sort: 25782ms Testing an array of length 100000 Quick sort: 8472ms Merge sort: 7437ms Insertion sort: 1010801ms Selection sort: 2361578ms Testing an array of length 100000 Quick sort: 96143ms Merge sort: 160642ms Insertion sort: 106746441ms Selection sort: 244460321ms
JavaTimer.java:
import java.util.Arrays;
import java.util.Random;
public class JavaTimer {
// Please expand method main() to meet the requirements.
// You have the following sorting methods available:
// insertionSort(int[] a);
// selectionSort(int[] a);
// mergeSort(int[] a);
// quickSort(int[] a);
// The array will be in sorted order after the routines are called!
// Be sure to re-randomize the array after each sort.
public static void main(String[] args) {
// Create and initialize arrays
int[] a = {1, 3, 5}, b, c, d;
// Check the time to sort array a
long startTime = System.nanoTime();
quickSort(a);
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000l;
// Output results
System.out.println("Working on an array of length " + a.length + ".");
System.out.println("Quick sort: " + duration + "us.");
}
// Thanks to https://www.javatpoint.com/insertion-sort-in-java
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;
}
}
// Thanks to
// http://www.java2novice.com/java-sorting-
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
// Thanks to http://stackoverflow.com/questions/13727030/mergesort-in-java
public static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length / 2;
// changed range of leftArray from 0-to-q to 0-to-(q-1)
int[] leftArray = Arrays.copyOfRange(A, 0, q - 1);
// changed range of rightArray from q-to-A.length to
// q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A, q, A.length - 1);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A, leftArray, rightArray);
}
}
private static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
// int[] a = new int[totElem];
int i, li, ri;
i = li = ri = 0;
while (i < totElem) {
if ((li < l.length) && (ri < r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
} else {
a[i] = r[ri];
i++;
ri++;
}
} else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
// return a;
}
// Thanks to: http://www.algolist.net/Algorithms/Sorting/Quicksort
public static void quickSort(int arr[]) {
quickSortRecurse(arr, 0, arr.length-1);
}
private static void quickSortRecurse(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSortRecurse(arr, left, index - 1);
if (index < right)
quickSortRecurse(arr, index, right);
}
private static int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
;
return i;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
