CSC152 2006S, Class 47: Quadratic Sorts

Admin:
* Homework 17: Sorting.
* Many of you had difficulty with homework 16, so we will discuss it.
  * Nothing from: Athanasakis, Gogo, Helmrich, Kim, Stevens
  * Minimal work from: McIntyre, Mendoza, Wang
* I will do my best to honor "Day of Silence" preferences.
* Titular Head stuff waits until later.
* EC for attending today's "Visualization" talk at 4:15.
* EC for attending tomorrow's convocation.

Overview:
* Dynamic programming and string matching.
* Review.
* Bubble sort, and why not to use it.
* Selection sort.
* Insertion sort.

/Dynamic Programming/

* Reduce running time by adding a cache that stores previously computed values
* What is the index into the cache?  The "value" that we're looking for
  * The "value" that we're recursing over

* Consider cost of best match algorithm
* What integers does it recurse over?
  * spos
  * tpos
* Since there are two values we recurse over, we need a two-dimensional array
  Use spos as first index and tpos as second index

* How do we typically use the cache, once we've created one and decided how to index it?
  * Before returning a value, store it in the cache
  * Before doing any serious computation, check the cache to see if we've already done the computation for that value

What's the running time of this algorithm?
How big is the cache?  O(source.length * target.length) 
If the two sizes are the same, O(n^2)

/Back to Sorting/

* Our goal:
  * Given a Vector
  * and a Comparator
  * Build a new Vector
  * That is a permutation of the original Vector
  * And is sorted.
* Test mechanism:
  * Build lots of sorted vectors
  * Permute them
  * Try to sort them
  * Compare
  * Missorted: Complain