Name _____________________ NetId __________
Section time _______________ Section instructor ___________________
Introduction
The goal of this lab is to show you how to time execution of a program and, with this new skill, to investigate the difference in execution time between linear search and binary search and between selection sort and insertion sort. Have a blank sheet of paper ready, to write on. Start a new folder for the .java files for this program and put in it these files (you can also get them from the Course web page for labs): Sorting.java TestArrays.java
Note: Class Sorting contains methods that you should learn by heart. You have to know most of them for the final. Don't memorize the code! Memorize any precondition
and postcondition and then develop the algorithm by first developing the loop invariant and then developing the loop parts using the four loopy questions.
Step 1. Learn about class Date
Package java.util contains a class Date, which can be used to record the current time. An instance of this class records a date in milliseconds (there are 1,000 milliseconds in a second) since 1 January 1970 (Greenwich mean time). Since there are 24 * 60 * 60 = 86400 minutes in a day, that's a lot of milliseconds since 1 January 1970! So, use type long to record such a number.
To see how this class is used, turn to method times in class TestArrays. The body includes two statements:
// Store in timeStart a Date with the time at which the statement is executed
Date timeStart= new Date();
// Store in timeEnd a Date with the time at which the statement is executed
Date timeEnd= new Date();
The next set of statements prints the values of these times in two forms. First, using method toString of class Date (applied automatically); second as an integer, which is obtained using method getTime. So you can see how many milliseconds have elapsed since 1 January 1970 (divide by 1000 to get the seconds).
To see the results of execution of these statements, execute the program. You'll see the results in the Java console. Note that the two times are exactly the same (or differ by at most 1). It takes very little time to allocate a new Date object and store its name in a variable.
Class Date is deprecated. This means that there is a more modern replacement for it but you can use it if you want. The problem with class Date is that it doesn't extend easily to international times. It is fine for our use here. If your DrJava gives warnings about deprecated classes and methods, you can turn the warning off using the preferences menu item.
Step 2. Experiment with searches
The first experiment you will make compares linear search with binary search. Look carefully at method testSearches and its specification. It executes linear search m times on the array, and executes binary search m times on the array. Execute the call TestArrays.testSearches(10); and see what execution prints in the Interactions Pane (and Java console).
The number 10 for m may be too small to see any results. It depends on how fast (or slow) your machine is. Increase it to 50, to 100, etc. until reasonable numbers until it takes between 5 and 10 seconds for linear search. When you get a reasonable number, write down m and this number on your sheet of paper.
To get a non-zero reading for binary search, keep increasing the value of m. For this purpose, you may want to fix the linear search
experiment so that it always does linear search 0 times, so you don't have to wait so long. How many times did binary search have to execute in order to get an elapsed time of around 5 or ten seconds? Write down these facts . Isn't it interesting, how fast binary search really is compared to linear search?
Step 3. Experiment with insertion sort and selection sort
Study method testSorts and its spec. It creates an array of size 5000, and then:
(0) runs selection sort m times on array b, each time initializing the array to {0, -1, -2, -3, ...}.
(1) runs insertion sort m times on array b, each time initializing the array to {0, -1, -2, -3, ...}.
Execute a call on testSorts with argument 5. Try higher values, like 10, 20, 30, etc., until it takes about 10-15 seconds to execute. Remember, we don't know how fast your computer is.
Write down on a piece of paper the value m and the times for each of the sorts.
Step 4. Experiment with sorting an already-ascending array
Look at method testSorts. In it, method fillneg is used to fill array b with values. There is also a method fillpos, which set the array to {0, 1, 2, 3, ...}. Change the method call fillneg(); (in two places) to fillpos(); , so that both selection sort and insertion sort will work on arrays that are already sorted and run the experiment again.
You will see that insertion sort takes a lot less time! Keep increasing m, the number of times each sorting method is executed, until finally you have a nonzero number for the insertion-sort time. Write down the results of the experiment on your sheet of paper.
Figure out WHY insertion sort is so quick when the array is already sorted. This requires looking at the code of insertion sort and of the method it calls and determining what happens if the array is already sorted. Write your explanation on your sheet of paper.
Step 5. Experiment with insertion sort and quick sort
Study method testSorts2 and its spec. It creates an array of size 75,000, and then:
(0) runs selection sort m times on array b, each time initializing the array to {0, -1, -2, -3, ...}.
(1) runs quicksort sort m times on array b, each time initializing the array to {0, -1, -2, -3, ...}.
Execute a call on testSorts with argument 1 –that should be high enough. It may take 30 seconds to a minute to time selection sort. Remember, we don't know how fast your computer is.
Write down on a piece of paper the value m and the times for each of the sorts. Remember, for an array of size n, selection sort takes time proportional to n*n and quicksort, on the average, takes time proportional to n log n.