The files ArrayList.java and SortableList.java contain the list implementation we have used in several assignments this semester. 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 SortedList.java class also has an empty method insertion sort that you should complete.
The insertion sort algorithm stores elements that have been inserted on the left side of the array and elements that have not been sorted yet on the right side of the array. Each iteration of the algorithm an element from the right, unsorted, side of the array is inserted (hence the name insertion sort) into the left side of the array such that the left side of the array is still sorted. This requires that all elements to the right of where the element is inserted be shifted to the right one place. When the algorithm begins the unsorted side of the array is all of the elements in the input array, and the sorted side of the array contains nothing. The algorithm is complete when the unsorted side of the array is empty and the sorted side of the array contains all of the elements. Complete the insertionSort method in the SortedList class.
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.
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 your lab5 directory and submit your code on the course Inquire site.