CSC152 2004F: Quadratic Sorts

Admin:
* Homework for Monday: Insertion sort
  * Get it in by 10:00 a.m.
* Food from another class

Overview:
* Testing, continued
* Selection sort
* Testing your code
* Insertion sort

/Testing: Look at the Code/

/Selection Sort/

* The key operation is "select" (the largest)
* Find the largest thing, shove it at the end
* Find the largest remaining thing, shove it at the previous spot
* Find the largest remaining thing, shove it at the previous spot
* Find the largest remaining thing, shove it at the previous spot
* Find the largest remaining thing, shove it at the previous spot
* Find the largest remaining thing, shove it at the previous spot
* ...
* Note that when we "shove" at a spot, we have a whole where it was and we have an old value from the spot: So we really swap
* Running time? O(n*n)
  * Finding the largest value is O(n)
  * Swapping is O(1)
  * We do those two operations O(n) times
* Implementation
  * Thanks Kyle!

/Testing, Revisited/

* Choose a Vector whose result you will know!
  * E.g., a permutation of the odd numbers
    * We've done the reverse of the odd numbers
  * Start with a vector in order, make a clone, permute the clone, sort it, and compare to the original