List Selection Sort

A selection sort is an in place algorithm for sorting. A selection sort works as follows:

• Find the minimum value in the list.
• Swap this value into the current position being sorted.
• Now we have a sub list that is sorted.
• epeat for the next position.

For example, given the following list:

72 4 67 15 19

Pass 1 of the algorithm swaps the 72 in position 1 with the 4 in position 2.

4 72 67 15 19

Now position 1 is sorted and we have a sub-list of sorted elements of size 1.

Pass 2 results in the following:

4 15 67 72 19

And so on until the list is sorted

4 15 19 72 67

In this lab you will use the 2 List class implementations from your text that we studied in class - ArrayList and LinkedList (both with exception handling). You will use the Selection Sort algorithm to sort data stored in instances of these lists. Make sure your code utilizes modular programming.

Part A:

• Create instances of an ArrayList and a LinkedList in your driver and fill each list with unsorted data read from a file.
• Add a procedure to your driver to sort a given list using a Selection Sort. Make your Selection Sort procedure more general by using ListInterface as the parameter type so you can pass both the ArrayList and LinkedList to the procedure for sorting.
• Display the contents of each list before and after the sort. Add printing methods to the 2 List classes to perform this task. Make sure your output is clear and neatly organized.

Note: Include try and catch blocks for calls to methods that throw exceptions.

Since the list classes are template classes that can be used with different data types, test your code with at least two different data types.

Part B:

Modify the LinkedList class by adding a public Selection Sort method to the class. You can test the new method using the LinkedList from part A filled with new data set or you can create an instance of a 3rd LinkedList in main.