CMSC 351 - "Thought Questions" - CMSC 351
Not Graded but Should be Done

1) Trace Counting Sort from the slies with the following input where (#,L) 
   should be seen as an object containing a key # and a data value L such 
   that the key # is what's "used" by counting sort's sorting part, but 
   where the entire object (or at least a reference to it) is what gets 
   copied around.
      [(4,A),(2,B),(8,C),(2,D),(15,E),(3,F),(2,G),(5,H),(13,J),(8,K),(20,M),(15,N),(8,P)]
   
   To do this in code, the posting Counting Sort code would be easily modified 
   to sort on a "key" and store references to the object associated with the 
   keys.  Implementing this as a library method for any object with a getKey() 
   method is an interesting programming project (that we won't be doing).



----wait until after Monday's lecture to think about the rest of these----




2) In each of the following scenarios select one of the sorting algorithms
   listed to use, and explain why you would use that one.

   You have a list of checks for a corporation, and that list 
   was created as the checks were cashed.  You now want to sort 
   the information based on the check number (increasing order).  
   Would you use QuickSort or SelectionSort or InsertionSort or 
   a version of Radix Sort?  Why?  How?

   You have a list of checks for a corporation, and that list 
   was created as the checks were cashed.  You now want to sort 
   the information based on the check amount (increasing order).  
   Would you use QuickSort or SelectionSort or InsertionSort or
   a version of Radix Sort?  Why?  How?

   You have a list of rooms on campus (like AVW3258, CSI3117) and
   when they are used.  They have been entered in the order of the 
   time of day that they are used, and the day of the week they 
   are used.  You now want to sort the information based on the room 
   code, "alphabetically".  Would you use QuickSort or SelectionSort 
   or InsertionSort or a version of Radix Sort?  Why?  How?








(3) Assume we have rooms with code like they are on campus such as 
    AVW1115 and HBK2117.  We are given a list of 1500 of these room
    codes and are asked to sort them 'alphabetically'.  How would 
    you define columns to allow for an 'optimal' radix sort as we
    have seen in class?  Assume that there is not a simple
    way to convert the building letter codes into sequential numbers
    and that you have to sort using the letter codes themselves.

       how to think about the solution