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