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."); } // // ############################################################### // // Standard implementations of sorting algorithms follow. // // ############################################################### // // 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-algorithms/selection-sort/ 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; } }

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."); } // // ############################################################### // // Standard implementations of sorting algorithms follow. // // ############################################################### // // 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-algorithms/selection-sort/ 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; } }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

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.");
}

//
// ###############################################################
//
// Standard implementations of sorting algorithms follow.
//
// ###############################################################
//

// 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-algorithms/selection-sort/
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;
}

}

A java class is provided below named Java Timer.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
с
d
e
Number of random integers
100
1000
10,000
100,000
1,000,000
User 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;
O
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 sor
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.
Your program output could look like the listing on the right.
Your 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 1000000
Quick sort: 96143ms
Merge sort: 160642ms
Insertion sort: 106746441ms
Selection sort: 244460321ms

Expert Solution

Step 1

Algorithm:

Define a class named "SortTimer" and import the necessary libraries.
Define a method named "InsertNumbersToArray" that takes an integer array as input and generates random integers (between 0 to 9999) to fill the array.
Define a method named "MeasureTime" that takes an integer array and an integer value "sortType" as input. Start the timer.
Use a switch statement to call the appropriate sorting algorithm based on the value of "sortType". Stop the timer. Calculate the duration by subtracting the start time from the end time. Return the duration.
Define a method named "randomizeArray" that takes an integer array as input and shuffles the elements randomly using the Fisher-Yates shuffle algorithm.
Define a method named "Testing" that takes an integer array as input. Print the length of the input array. Measure the time taken to sort the input array using quick sort algorithm and print the duration.
Randomize the input array using the Fisher-Yates shuffle algorithm. Measure the time taken to sort the input array using merge sort algorithm and print the duration.
Randomize the input array using the Fisher-Yates shuffle algorithm. Measure the time taken to sort the input array using insertion sort algorithm and print the duration.
Randomize the input array using the Fisher-Yates shuffle algorithm. Measure the time taken to sort the input array using selection sort algorithm and print the duration.
Define the main method. Create five integer arrays of different lengths. Generate random integers to fill each array using the "InsertNumbersToArray" method.
Call the "Testing" method for each array.

Step by step

Solved in 4 steps with 6 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.