The file Sorting.java contains a static method, selectionSort, that is an adaptation of the sorting method you created in a previous lab to sort a deck of cards. Can you tell what is different between this method and the one you created? (Hint: this one uses less memory, but why?) Also note the method does not return an array, so how does the calling method sort an array with this method? (Hint: arrays are objects) The program SortingTest.java creates an array of Strings from random numbers and uses the selectionSort method to print a sorted version of the array. Run the program and note that it does not work properly. You may have to run it multiple times to generate an error. There is a logic error (or bug) in the sorting code. Use the debugger in Eclipse to find the problem and fix it.
Once you have found and fixed the problem, double the size of the array and test it again. You may have to run it multiple times. Notice anything strange? It doesn't work again. Why not? (Hint: lexographic ordering) To fix it actual numbers should be put into the array instead of strings. However, the selectionSort method takes an array of objects that implement Comparable, and ints are not Comparable. What to do? (Hint: Recall wrapper classes from CS120?) Wrapper classes are subclasses of Object that reprsent primitive data types. Java has a feature called autoboxing that does automatic type conversion between primitive types and their corresponding wrapper types. Autoboxing is briefly explained on page 100 of the text. So if you create an array of type Integer it is possible, because of autoboxing, to add ints to it. Modify SortingTest so that it takes advantage of the autoboxing feature to generate and sort an array of Integers.
The selectionSort method implements an 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 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 Sorting class also cotains a stub for an implementation of the insertion sort algorithm, insertionSort. 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. Use the SortingTest class to test the insertionSort 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. (Coincidentaly, last Friday at 23:31:30 the method returned 1234567890000.) 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 ammount 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.
Run the program several times and notice that the methods do not return the same duration every time. Do you know why this is? (Hint: there are several reasons) 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. Put your average sort time code inside a loop that increases the number of time trials until they are consistantly 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?
Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab6 in the subject.