Remember that timing can be tricky for a variety of reasons. For this assignment we will design tests and collect samples until a minimum amount of time has elapsed. Pay attention to the following guidelines:
Algorithm: makeRandomTestCreate a separate method to generate each type of sequence.
Input: n - the number of elements in the random test sequence
Output: s - a sequence of n random numbers in the range 0 to 100,000
// Create the test sequence:
Sequence s = new Sequence()
java.util.Random random = new java.util.Random();
// Initialize the Sequence:
for i=0 to n-1
s.addLast(random.nextInt(100000));
Algorithm: testInsertionSortFor this project use a minimum time of 500,000 nanoseconds (1/2 s).
Input: s - a sequence to use for empirical measurement of insertion
sort
Input: minimum time - the minimum amount of time to run tests
Output: average time taken
System.gc() // Force java to Garbage Collect
samples=0 // No samples yet
start = current time // Begin stopwatch
do {
insertionSort(s) // Sort the data
samples++
stop = current time
} while(stop-start < minimum time);
average time = (stop-start)/(1.0*samples)
return average time
This will give you a total of 39 "times", 13 for each sort. You will need to plot 3 lines, one for each sort, so be sure that the data is stored or displayed in a way that makes this easy. For example, something like
System.out.printf("%4d , %7.5f , %7.5f , %7.5f %n", n, selectionTime, insertionTime, heapTime);
will allow you to import the columns of data into a
spreadsheet as a "comma separated value" (CSV) file.
Again, you will give you a total of 39 "times", 13 for each sort.
Again, you will give you a total of 39 "times", 13 for each sort.
Example: 10% of n=50 is 5:
for i=0 to 5
pick random location 1
pick random location 2
swap the data between 1 and 2
Again, you will give you a total of 39 "times", 13 for each sort.
Consider the following checklist: