This program involves using STL lists.
For this program you will implement three functions whose prototypes are given below:
list::iterator mxIter(list::iterator first,
list::iterator last);
void selectSort(list& aList);
void writeList(const list& alist);
What you need to do:
You are going to use a static array declared using { 12, 1, 6, 8, 5, 9, 22, 9, 13, 17 } to initialize an STL list, as shown in the slides.
Then you will implement a selection sort (selectSort). A selection sort involves sweeping over the list and finding the maximum element of the list (by calling MxIter) that has not already been sorted, creating a new element at the beginning of the list, setting its value to be the same as the maximum element's value, and then deleting the maximum element (using erase).
Note that you need to keep track of the beginning of the unsorted part of the list. This is straightforward unless the beginning of the unsorted part of list needs to change due the the erasing of the node currently at the beginning of the unsorted part of the list, i.e. you don't need to change this iterator unless it is "pointing" at an element of the list that will be deleted.
The creation of a new node at the front of the list and deletio of a node in the unsorted part of the list occurs n times, where n is the size of the list. Note that in the nth iteration, the smallest element in the original list is moved to the beginning of the sorted list. When the sorting is completed, the list will contain, from left to right, minimum element to maximum element.
The function mxIter is called to find the maximum element in the unsorted part of the list. It returns an iterator that "points" to the maximum element.
The writeList function is used to print out the initial contents of the list and the final contents of the list. The output of the program should be:
Unsorted list: 12 1 6 8 5 9 22 9 13 17
Sorted list: 1 5 6 8 9 9 12 13 17 22