Lab 4: ArrayLists and Lists

Goal: To become familiar with the strengths and weaknesses of different collection types (ArrayLists and Lists) by implementing them and trying three basic collection operations, sorting, searching, and inserting. In order to see the performance differences of these algorithms, a large collection of Cities will be used.

Part 1 - The Opening

Open up the lab. The main files/classes in that lab that we'll be working with is AAlgorithms, which is abstract and should have two children, ArrayListAlgorithms and ListAlgorithms. It is in these three classes that you'll need to add the code to insert, sort, and search. You'll also probably want to go to java.sun.com (hint hint!) and look up the API for ArrayLists.

Part 2 - Insertion

The first thing we want our Algorithms to do is be able to insert values into an ArrayList or List. For the purposes of this part of the assignment, we'll assume that inserted values can be added anywhere in the Collection, so where they are placed doesn't matter.

Implement an abstract method insert into both of the child classes of AAlgorithms, what does this function consume and produce?

Part 3 - Sorting

Next, we want to be able to sort our data so we can easily locate information within the Collection. There are two types of sorts we want to implement:

InsertionSort
 In an insertion sort, the data that we are sorting gets processed one piece at a time. We start from one end of the array/list, and insert that value. When we only have one value, the insertion does not change anything. After this, we proceed onward and insert the next value. Into our previously sorted values. We proceed onward until we have inserted all of the data, and the entire list is sorted.
MergeSort
 In a merge sort, we use a divide and conquer approach to solving our problem. We split the data into two equal parts, and then sort each of these halves in the same manner. Once we have divided all of the data into single items, we can begin the actual merging of the sorted pieces. The data is paired off and merged together. This continues with larger and larger pairs until we are back up to the base split we made in the data. Once those two sections have been merged, the data is sorted.

Implement these two sorting strategies for both of the Collection types. If you have any questions on them, ask the lab instructor.

Merge Sort
Insertion Sort

Part 4 - Searching

Searching is also an important feature, and its speed can normally be improved if you have a sorted collection. We want to implement sorting for both ArrayLists and Lists.

Add a search function to the AAlgorithms class, can you think of any way the search can be optimized because the List is sorted, because the ArrayList is sorted?