CSC152 2006S, Class 46: Sorting

Admin:
* Homework 16: Approximate String Matching.
* We'll try the mini-Titular Head again tomorrow.
* Advance notice: Exam 3 distributed Friday.
* Taking more CS?
  * Natural fall course: CSC223 (Software Design) (Staff)
  * Alternate fall course: CSC205 (Computational Linguistics) (Stone)

Overview:
* The Problem of Sorting.
* Carefully Specifying Sorting Methods.
* Testing Sorting Methods.

What does it mean to sort?
* Given a collection, put the elements in a particular order
  * What do we mean by a collection?
    * Array
    * Vector
    * Sequenced Lists
  * What do we mean by "in order"?
    * "According to a comparator"
      * c.compare(a[i],a[i+1]) <= 0 for all reasonable i
      * c.compare(v.get(i),v.get(i+1)) <= 0 for all reasonable i
      * c.compare(l.get(pos),l.get(l.successor(pos))) <= 0
    * Using the "internal comparator" of Comparables
      * a[i].compareTo(a[i+1]) <= 0 for all reasonable i
    * We should be able to predict the order in which the elements appear
* Questions when designing a sorting algorithm:
  * What are we sorting?  For this class: Vectors
  * How do we compare?  For this class: Using a Comparator 
  * In-place (mutate)?  New vector (maybe some in-place examples, too)
  * Stable?  If A precedes B before the sort, and A = B, where does A appear after the sort?  Not required, but analyzed.
    * Example: Sort by date, then sort by name.  Within each name, a stable sort keeps them sorted by date.

public interface Sorter<T>

/**
 * Sort a vector in increasing order.
 *
 * @param vec
 *   The vector to be sorted.
 * @param c
 *   The comparator that determines the order.
 * @return sorted
 *   The sorted version of vec.
 * @pre
 *   The vector is non-empty.  (vec.length() > 0)
 *   The comparator should be applicable to any two elements in vec.
 *     (c.compare(vec.get(i),vec.get(j)) does not throw an
 *      exception for any valid i and j).
 *   The comparator is transitive and reflexive and all that stuff.
 * @post
 *   sorted is sorted.
 *     c.compare(vec.get(i),vec.get(i+1)) <= 0 for any reasonable i 
 *      (0 <= i < vec.length()-1)
 *   sorted is a permutation of vec.
 */
public Vector<T> sort(Vector<T> vec, Comparator<T> c);

}

Black-box testing: What tests do you want to run?
* Give it one vector and see if it sorts correctly.
  * Use human brain.
  * Automate testing:
    * Is it sorted?
      public boolean sorted(Vector<T> vec, Comparator<T> c)
      {
        for (int i = 0 ; i < vec.length()-1; i++) {
          if (c.compare(vec.get(i),vec.get(i+1)) > 0) {
            return false;
          }
        } // for
        return true;
      }
    * Is it a permutation?
      Put each element in a dictionary (one for original list, one for sorted list) with a counter , ...
      * Start with a sorted vector.
      * Make a copy and permute the copy
      * Ask to sort the permuted copy
* Give it a presorted vector and see if it comes out unchanged.
* Try a variety of lengths
* Try with and without duplicates

* How would you permute the copy of the already-sorted vector?
  * Repeatedly
    * Use a random number generator
    * Use that rng to pick positions
    * Swap the values at that positions