Using the class StopWatch: import java.util.Random; public class StopWatch { pri
ID: 3671333 • Letter: U
Question
Using the class StopWatch:
import java.util.Random;
public class StopWatch {
private long startTime;
private long endTime;
public static void main(String[] args) {
int[] list = new int[100000];
Random random = new Random();
// Fill list with random 100,000 integers
for(int i = 0; i < list.length; i++) {
list[i] = random.nextInt(100);
}
// Start timer and sort
StopWatch stopwatch = new StopWatch();
selectionSort(list);
stopwatch.stop();
System.out.println((stopwatch.getElapsedTime() / 1000) + "s");
}
// No-arg, initializes startTime
StopWatch() {
startTime = System.currentTimeMillis();
}
void start() {
startTime = System.currentTimeMillis();
}
void stop() {
endTime = System.currentTimeMillis();
}
long getElapsedTime() {
return endTime - startTime;
}
public static void selectionSort(int[] x) {
for(int i = 0; i < x.length; i++) {
int minIndex = i;
for(int j = i + 1; j < x.length; j++) {
if(x[minIndex] > x[j]) {
minIndex = j;
}
}
if(minIndex != i) {
int temp = x[i];
x[i] = x[minIndex];
x[minIndex] = temp;
}
}
}
}
Using the TestSearch (given) plug in the class (StopWatch):
import java.util.*;
public class testSearch {
public static void main(String[] args){
// input array size from user
Scanner input = new Scanner(System.in);
System.out.print("Enter array size: ");
int size = input.nextInt();
System.out.println();
// create the array (the numbers do not really matter)
int[] numbers = new int[size];
for(int i=0; i<numbers.length; i++){
// we want the numbers sorted for binary search
// so why not just the numbers 0,1,...,size-1
numbers[i]=i;
}
// store the time now
long startTime = System.nanoTime();
// linear search for size (which is not in the array)
linearSearch(numbers,size);
// display the time elapsed
System.out.println("The time taken by Linear Search is " + (System.nanoTime() - startTime) + "nanoseconds.");
// prepare to measure the time elapsed again
startTime = System.nanoTime();
// binary search for size
binarySearch(numbers,size);
// display the time elapsed
System.out.println("The time taken by Binary Search is " + (System.nanoTime() - startTime) + "nanoseconds.");
}
public static boolean linearSearch(int[] a, int key) {
for(int i=0; i<a.length; i++){
if(a[i]==key) return true;
}
return false;
}
public static boolean binarySearch(int[] a, int key) {
int low = 0;
int high = a.length -1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid]>key) {
high = mid - 1;
} else if (a[mid]<key) {
low = mid + 1;
} else {
return true;
}
}
return false;
}
}
Explanation / Answer
save the following program as StopWatch.java
import java.util.Random;
public class StopWatch {
private long startTime;
private long endTime;
// No-arg, initializes startTime
StopWatch() {
startTime = System.currentTimeMillis();
}
void start() {
startTime = System.currentTimeMillis();
}
void stop() {
endTime = System.currentTimeMillis();
}
long getElapsedTime() {
return endTime - startTime;
}
public static void selectionSort(int[] x) {
for(int i = 0; i < x.length; i++) {
int minIndex = i;
for(int j = i + 1; j < x.length; j++) {
if(x[minIndex] > x[j]) {
minIndex = j;
}
}
if(minIndex != i) {
int temp = x[i];
x[i] = x[minIndex];
x[minIndex] = temp;
}
}
}
public static void main(String[] args) {
int[] list = new int[100000];
Random random = new Random();
// Fill list with random 100,000 integers
for(int i = 0; i < list.length; i++) {
list[i] = random.nextInt(100);
}
// Start timer and sort
StopWatch stopwatch = new StopWatch();
selectionSort(list);
stopwatch.stop();
System.out.println((stopwatch.getElapsedTime() / 1000) + "s");
}
}
output generated is:
sh-4.3$ javac StopWatch.java
sh-4.3$ java StopWatch
9s
_____________________________________________________________
save the following program as testSearch.java in the same directory
import java.util.*;
public class testSearch {
public static void main(String[] args){
// input array size from user
Scanner input = new Scanner(System.in);
System.out.print("Enter array size: ");
int size = input.nextInt();
System.out.println();
// create the array (the numbers do not really matter)
int[] numbers = new int[size];
for(int i=0; i<numbers.length; i++){
// we want the numbers sorted for binary search
// so why not just the numbers 0,1,...,size-1
numbers[i]=i;
}
// store the time now
long startTime = System.nanoTime();
// linear search for size (which is not in the array)
linearSearch(numbers,size);
// display the time elapsed
System.out.println("The time taken by Linear Search is " + (System.nanoTime() - startTime) + "nanoseconds.");
// prepare to measure the time elapsed again
startTime = System.nanoTime();
// binary search for size
binarySearch(numbers,size);
// display the time elapsed
System.out.println("The time taken by Binary Search is " + (System.nanoTime() - startTime) + "nanoseconds.");
}
public static boolean linearSearch(int[] a, int key) {
for(int i=0; i<a.length; i++){
if(a[i]==key) return true;
}
return false;
}
public static boolean binarySearch(int[] a, int key) {
int low = 0;
int high = a.length -1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid]>key) {
high = mid - 1;
} else if (a[mid]<key) {
low = mid + 1;
} else {
return true;
}
}
return false;
}
}
The following output generted.
sh-4.3$ javac testSearch.java
sh-4.3$ java testSearch
Enter array size: 11
The time taken by Linear Search is 175457nanoseconds.
The time taken by Binary Search is 13389nanoseconds.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.