Using the System class introduced in our lab session and the insertion sort prog
ID: 3861790 • Letter: U
Question
Using the System class introduced in our lab session and the insertion sort program discussed in our lecture to report the elapsed time when we use insertion sort program to sort n integers, where n is an integral number input by the user of your program and each integer is between 0 and 99999 inclusive. The following is a sample run of your program.
Input a number (at least 1000):
3000
Insertion sort needs 20 milliseconds to sort 3000 integers.
Continue ? (Yes/No) Yes
Input a number (at least 1000):
20000
Insertion sort needs 611 milliseconds to sort 20000 integers.
Continue ? (Yes/No) No
Explanation / Answer
InsertionSortTime.java
import java.util.Random;
import java.util.Scanner;
public class InsertionSortTime {
public static void main(String[] args) {
String s = "Yes";
Scanner scan =new Scanner(System.in);
while(s.equalsIgnoreCase("Yes")){
System.out.println("Input a number (at least 1000): ");
int n = scan.nextInt();
int a[] = new int[n];
Random r = new Random();
for(int i=0; i<n; i++){
a[i]=r.nextInt(100000);
}
long startTime = 0;
long lastTime = 0;
startTime = System.currentTimeMillis();
insertionSort(a);
lastTime = System.currentTimeMillis();
System.out.println("Insertion sort needs "+(lastTime - startTime)+" milliseconds to sort "+n+" integers.");
System.out.println("Continue ? (Yes/No): ");
s=scan.next();
}
}
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;
}
}
}
OUtput:
Input a number (at least 1000):
3000
Insertion sort needs 61 milliseconds to sort 3000 integers.
Continue ? (Yes/No):
yes
Input a number (at least 1000):
20000
Insertion sort needs 125 milliseconds to sort 20000 integers.
Continue ? (Yes/No):
no
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.