CSC152 2004F, Class 44: An introduction to Sorting

Admin:
* Homework 45: Some simple sort (insertion sort or selection sort)
  * Turn it in by 10:00 a.m. so I can use it for class discussion.

Overview:
* The problem, in general
* The problem, formalized
* Testing

/The problem of sorting/

* Take a collection (buncha) stuff and put it in order
* Lots of ways to think about this problem in programming terms
  * What is a "buncha stuff"
    + Vector ***
    + List
    + Array
    + Tree (sometimes)
    + Note: Sorting of vector, array, or list can be turned into sorting of one of the others through a few O(n) operations
  * How do we express "in order"?
    + Use a comparator to check the ordering  ***
    + Use only numbers and the <= operation
    + Use only Comparable things and their "natural" order (given by compareTo)
  * Where do we get the particular comparator to sort?
    + Callback to caller ("Hey, what comparator did you want me to use?")
    + Parameter to the sort method
    + Field specified in constructor ***
  * When you sort a collection, do you change the collection or create a new collection?
    + We'll use inplace ***
  * Implementation question (stability): if a has a lower index than b inthe collection before we sort it and the comparator says that a equals b, does a still have a lower index than b after sorting?
    + Why would we care about such a question?  Because it lets us do two subsequent sorts and get a result that combines the two of them (sort by date and then by user gives us a result that is sorted by user, but the results for a user are in order by date)
    + Why would we not want to guarantee such a result?  It's easier to implement something with fewer guarantees. ***
  * Ascending or descending order
    + Ascending ***

/Formalize!/

* See sample code
* Question: When a comparator cannot compare two things, what exception does it throw?  Traditionally, a ClassCastException