Topical Information

This lab will help you practice with vectors.

Program Information

Code both the selection sort (from Chapter 6/online notes) and the insertion sort (from Chapter 6/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).

Options

• Add (Level 0.5) to allow the user to specify the bounds of the range for the random values you are filling the vector with.
• Add (Level 0.5) to allow the user the option of filling the vector randomly (as it is now) or entering the data by hand. If they are entering the data by hand, you should use a fail or special-value termination loop for data entry — don't have them enter the number of values up front.
• Add (Level 1.5) to use the time function to decide how fast the two sorts are. (Increase this by another (Level 1.5) to use the second method mentioned in the timing notes.)

  More Thought Provoking Questions

  1. Which seems fastest?
  2. How do you determine how long something took using the time function?
  3. How can you ensure accurate timings? (Hint: Average over MANY trials.)
  4. How can you ensure that your timings are comparable? (i.e. when taking multiple timings, does it make sense to time two things that aren't the same? Would it make sense, for instance, to compare the time it takes Jose to wash a car and the time it takes him to wash a semi-truck? They are both vehicles... What about to compare Ng's time to Maeve's time if both wash minivans? What if Maeve washes the same minivan right after Ng gets done?)
• Add another (Level 1.5) to use your Timer class to perform the timing. (This can be combined with either of the previous timing options above.)
• Add (Level 1) to develop functions which can generate random floating point values within a specified range and random characters within a specified range. Place these functions in a library. Create a small test program to make sure they are working. Hint:

      inline long rand_range(long low, long high)
      {
          return low + rand() % (high - low + 1);
      }
  
      inline double rand_range(double low, double high)
      {
          // may call 'long' version
      }
  
      inline char rand_range(char low, char high)
      {
          // may use type-casting and call 'long' version
      }
  

  Will your random library need an implementation file? Why/Why not? (Hint: for the double version, it might help if you had an intermediate function called rand_01().)
• Add (Level 1.5) to do the bubble sort as well. (Include all the standard overloaded versions required for the original two sorting algorithms and test them both explicitly.)
• Add (Level 1.5) to do the three variations of the bubble sort algorithm described in its own special notes entry and test them explicitly. (Note: The variations will have two overloads each and so will need separate names from the original standard bubble sort — if you do that option as well.)
• Add (Level 1.5) to make a menu for the user from which they can choose which sorting algorithm (or variation thereof) to test. A good basic structure for this menu might be:

      1) Enter Number of Elements with which to test
      2) test Selection sort
      3) test Insertion sort
      4) Quit
  

  You will just have to add more options to the user's menu (before the quit option...) if you've chosen to do more sorting algorithms as offered above. Note that the first option may change/become multiple options if you've done certain options affecting the vector contents above.
  As with any menu, you should allow the user to choose their option by either the number or special letter(s) of the option (denoted in the example by capitalization).
• Add another (Level 0.5) to make a sub-menu for each sort testing menu option to select which of the overloads to test. Perhaps something like:

      Selection Sort
  
      1) test via Whole vector
      2) test via Size_Types
      3) test via All overloads
      4) Nevermind
  

  Note how the sorting algorithm that was to be tested acts as the sub-menu title. The 'all overloads' option performs testing by all three overloaded versions of the algorithm and reports the results. The 'nevermind' option simply returns to the main menu without testing this sort after all.
  As with any menu, you should allow the user to choose their option by either the number or special letter(s) of the option (denoted in the example by capitalization).
• Add another (Level 1.5) to make the sub-/menus all work through a single menu printing/inputting function. This function should print the sub-/menu and return an integer representing the user's choice from the sub-/menu. The calling part of the program will then use that integer to decide what function(s) to call/test. (Hint: Is there any similarity among the various sub-/menus for the various algorithms? What difference(s) are there — in the sub-/menus themselves?)