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