Topical Information

This lab will help you practice with vectors.

Program Information

Code both the selection sort (from Chapter 15/online notes) and the insertion sort (from the online notes). Place these two sorts in a library.

You should have two versions of each (overloading one another): one takes a whole vector and sorts it and another takes the whole vector and beginning and ending size_type positions of a range of elements to be sorted. One of these can be inline and call the other. (I wonder which is the most generic of the two...?)

Write a driver to [effectively] test all four sorts. Have it ask the user how many values are to be sorted, then randomly generate values to fill in the vector (up to their specified size), sort them with the function you are currently testing, verify that the values are indeed sorted, and tell the user the results. Only print the sorted vector if the user says they want you to.

Thought Provoking Questions

  1. Explain (briefly) the differing philosophies of selection and insertion sort. How can they both produce a sorted list?
  2. What type of values are your functions sorting? Does it really matter what type it is in terms of the algorithms? Does it make very much of a difference to your implementation of the algorithms? How easily could you change the type of information you were sorting? (Is there a special type of data that might be more difficult to adjust to?)
  3. Does it matter what range of values you produce to randomly fill the vector? Will this affect the sorting in any way?
  4. Do your functions sort into ascending or descending order? How would you go about changing this order? As long as it is 'in order', does it truly matter which direction they are going?
  5. How can you do the verification that the data is sorted? (Note that your program is supposed to do this automatically -- not ask the user if the data is sorted after printing it!)

This assignment is (Level 4).