Homework: Queue III; Selection Sort

This homework is necessary preparation for the lab. Make sure you type your answers in a file you bring to the lab so that you will be able to quickly copy and paste them into the file provided in the lab.

1. Implement the static method removeMin declared as follows:

   /**
    * Removes and returns the minimum value from {@code q} according to the
    * ordering provided by the {@code compare} method from {@code order}.
    * 
    * @param q
    *            the queue
    * @param order
    *            ordering by which to compare entries
    * @return the minimum value from {@code q}
    * @updates q
    * @requires <pre>
    * q /= empty_string  and
    *  [the relation computed by order.compare is a total preorder]
    * </pre>
    * @ensures <pre>
    * perms(q * <removeMin>, #q)  and
    *  for all x: string of character
    *      where (x is in entries (q))
    *    ([relation computed by order.compare method](removeMin, x))
    * </pre>
    */
   private static String removeMin(Queue<String> q, Comparator<String> order) {...}
   

   To compare two Strings, use the Comparator<String> method compare (see Slides 45-50 in Queue). Do not call sort in your code for removeMin, as this would miss the point of the problem; see below.

2. Implement the static method sort declared below that sorts a Queue<String> q using the "selection sort" algorithm according to the given order. This algorithm repeatedly calls removeMin until q is empty, placing the items it returns one-by-one into a temporary queue, and then finally transferring this temporary object into q.

   /**
    * Sorts {@code q} according to the ordering provided by the {@code compare}
    * method from {@code order}.
    * 
    * @param q
    *            the queue
    * @param order
    *            ordering by which to sort
    * @updates q
    * @requires [the relation computed by order.compare is a total preorder]
    * @ensures q = [#q ordered by the relation computed by order.compare]
    */
   public static void sort(Queue<String> q, Comparator<String> order) {...}