/*************************************************************************
* Name:
* Login:
* Precept:
*
* Description: The method timeTrials() runs InsertionSort.sort() for
* arrays of random double values. The first argument to the method is
* the number of trials; the second argument is the length of the array.
* Multiple trials produce more accurate results because insertion sort's
* running time depends on the input and various system effects.
*
* Dependencies: StdOut.java
*
* Examples:
* % java InsertionTest 10
* 1024 1.89
* 2048 5.00
* 4096 3.58
* 8192 4.09
* 16384 4.83
* 32768 3.96
*************************************************************************/
public class InsertionTest {
// runs InsertionSort.sort() for arrays of random double values
public static double timeTrials(int M, int N) {
Double[] a = new Double[N];
double total = 0;
for (int k = 0; k < M; k++) {
for (int i = 0; i < N; i++)
a[i] = Math.random();
Stopwatch s = new Stopwatch();
Insertion.sort(a);
total += s.elapsedTime();
}
return total;
}
public static void main(String[] args) {
int M = Integer.parseInt(args[0]);
double prev = timeTrials(M, 512);
for (int N = 1024; true; N += N) {
double curr = timeTrials(M, N);
StdOut.printf("%7d %4.2f\n", N, curr / prev);
prev = curr;
}
}
}