The file ArrayList.java contains
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 ArrayList 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.
Before writing any code, make sure that you understand how the algorithm works. It can help to try it out on a small example using pen and paper. Some other things that you should consider before proceeding. How will you represent where the sorted elements in the list end, and where the unsorted elements begin? Would the program be any easier to write if you first create a private helper method to do some of the work? Be sure to test your code. Create a program that creates and ArrayList of Integers, add ints to it, shuffles the list, sorts the arrray, and finally prints the list.
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 list 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 lists, by creating a second list and copying every
element in the list.
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. If you can run your program twice and the result is not the same you should increase the number of trials. Is the difference in the algorithms what you expected? Can you explain the difference?
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.