Search and Sort Algorithms

Objectives - To test search and sort algorithms

As you add methods to the code given, add documentation similar to what is used on the other methods (comment boxes).

Turn in IntegerList and IntegerListTest, table filled in, and the answer to a question on sorting and searching - see step 8 below.

1. The selection sort is missing two methods (swap and minIndex) - add them or copy the code for a selection sort using one method from last week's lab. Use this selection sort code in the sortAscending method.

2. Write the insertion sort, changing the insertion logic to sort in descending order and use it for sortDecreasing method. (p. 523).

3. Make sure the selection sort is increasing order and the insertion sort is decreasing order by creating small arrays, sorting them, and then printing them.

4. Write a method that to implement the enhanced bubble sort that sorts in ascending order.

5. Sort an array filled with random numbers with the selection sort for the first timing and then sort it again with the selection sort for the second timing.

6. Sort an array filled with random numbers with the insertion sort for the third timing and then sort it again with the insertion sort for the fourth timing.

7. Sort an array filled with random numbers with the enhanced bubble sort for the fifth timing and then sort it again with the enhanced bubble sort for the sixth timing.

8. Remember that the data in an array must be in ascending sequence to search it with the binary search method. Fill the arrays with sorted data before calling the binary search method. Since it doesn't matter if you fill the arrays to be used with the sequential search with sorted or unsorted data, you might as well fill the search array with sorted data once, then sequentially search it and then binary search it.

9. Write a short paragraph on sorting and another on searching. Explain why the times changed (or didn't change) for the different methods and how the algorithms were affected by the larger array sizes.

Timing Searching and Sorting Algorithms

In this exercise you will use an IntegerList class (in the file IntegerList.java) and a driver (in the file IntegerListTest.java) to examine the runtimes of the searching and sorting algorithms. The IntegerListTest class has several options for creating a list of a given size, filling the list with random integers or with already sorted integers, and searching or sorting the list. (NOTE: You may have used a version of these classes in the last lab.) Save these files to your directory and run IntegerListTest a few times to explore the options.

The runtimes of the sorting and searching algorithms can be examined using the Java method System.currentTimeMillis(), which returns the current system time in milliseconds. (Note that it returns a long, not an int.) You will have to import java.util.* to have access to this method. In IntegerListTest, just get the system time immediately before and immediately after you perform any of the searches or sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds. WARNING: Be sure you are not including any input or output in your timed operations; these are very expensive and will skew your algorithm times!

Add appropriate calls to System.currentTimeMillis() to your program, run it and fill out the tables below. Note that you will use much larger arrays for the search algorithms than for the sort algorithms; do you see why? Also note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs. On a separate sheet, explain the times you see in terms of the known complexities of the algorithms. Remember that the most interesting thing is not the absolute time required by the algorithms, but how the time changes as the size of the input increases (doubles here).