Lab 2 - I've Got A Little List Part I
A selection sort is an in place algorithm for sorting. A selection sort works as follows:
1. Find the minimum value in the list
2. Swap this value into the current position being sorted.
3. Now we have a sub list that is sorted.
4. Repeat for the next position.
For example. Given the
following list:
72 4 67
15 19
Pass 1 of the algorithm swap the 33 in position 1 with the 4.
4 72 67 15 19
Now position 1 is sorted and we have a sub list of sorted
elements of size 1.
4 72 67
15 19.
Pass 2 results in the following.
4 15 67
72 19
And so on until the list is sorted.
4 15 19
72 67
4 15 19
67 72
This lab will use the different List class implementations we
have studied. The goal of this lab is to
demonstrate GOOD MODULAR programming. We
will implement a selection sort using several different List class
implementations.
Part A - Using the array based List Class (ArrayList.h
and ArrayList.cpp), write a function, that is passed a List object as a
parameter, that will sort the List using a Selection Sort. Put the code for your function in your driver
file.
Display the list contents before the sort and after. Make sure your output is clear and neatly
organized.
Create your initial List by reading values from a data
file. Since our list classes can be used
with different data types, run your code
on at least three different data types (i.e. string, int, char, float, etc.)
Part B - IF you wrote nice, modular code, you should be able to
modify your selection sort to use a List class that implements exception
handling.
Redo Part A using the array implementation of the List class
with user defined exception handling (ListA.h and
ListA.cpp). How many lines of code did
you have to change? (YES I want you to
TELL me this number. Place a comment at
the start of your driver file with this info.)
Repeat using the dynamic array with the standard exception
classes. How many lines of code did you have to change? (YES I want you to TELL me this number. Place a comment at the start of your driver
file with this info.)
Hand in the code for ALL
parts A and B along with printouts of the data files used to test your code,
and the respective outputs. Make sure
you put a comment at the start of your driver file indicating which List
implementation is being tested and how many lines of code were APPROXIMATELY
changed.