The file Array.java contains the static methods we created in class for use with arrays. The sort method has been renamed to selectionSort because it uses the selection sort algorithm. An algorithm is a sequence of computational steps for completing a task. In this case the task is to order all of the elements in an array. There are many different algorithms for performing this same task; each has its own advantages and disadvantages over other algorithms. The parameter iterations has also been added to the selectionSort method. This is used to specify the number of iterations of the sort to perform. This will be useful in the post-lab.
The insertion sort algorithm sorts an array by repeatedly inserting unsorted values into an already sorted array. With each iteration the first element in the unsorted array is removed and added to the sorted array (in the proper place to maintain the sort). When the algorithm begins the unsorted array is all of the elements in the input array, and the sorted array contains nothing. The algorithm is complete when the unsorted array is empty and the entire input array is in the sorted array. Before proceeding make sure that you understand the algorithm.
The Array class also contains a stub for an implementation of the insertion sort algorithm. Fill in the code for insertionSort. Be sure that your code sorts the input array in-place, like the selectionSort method, so it does not need to create a separate sorted array. Instead, your code should store the unsorted array on one side of the input array and the sorted array on the other side of the input array. Be sure to test your method.
Can you tell which sorting algorithm, selection or insertion, is faster at sorting by looking at the code? Create a program to test your intuition. The static method currentTimeMillis in the System class returns a long that is the number of milliseconds since January 1st 1970. By checking what the current time is before and after calling a sorting method it is possible to determine how many milliseconds the sort took. Create a class, SortingTime, that creates an array of random Integers, sorts it using both selection and insertion sort, and displays the amount of time that each method took. If the methods return a result that is the same, increase the size of the array they have to sort. Make sure that both methods are sorting identical random arrays. You can use the copy method in the Array class to create two arrays with the same contents.
Run the program several times and notice that the methods do not return the same duration every time. Do you know why this is? To compensate for this variation, test each of the sorting algorithms many times and take the average. You could do this by running it repeatedly, writing down all of the results, and then computing the average, but it would be easier to program a loop to do this for you. Make sure that each time through the loop the array the algorithm is being tested on is not already sorted. Also make sure that the time spent initializing or shuffling the array is not included in the time measurement.
How many time trials should be averaged together to get an accurate reading? You need to figure this out. As the number of trials that are averaged together is increased the variation in the average goes down. Put your average sort time code inside a loop that increases the number of time trials until they are consistently the same. This is called the steady-state. In this case we will say that the steady state is reached when the average time does not change for 10 consecutive trial sizes. Have your program print the results of the steady-state time for each of the sort algorithms. Is this what you expected?
To submit your code: Tar the files in your lab5 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab5. Be sure to name the tar file with your names, not lab5.tgz.