CSC151.02 2013F, Class 47: Insertion Sort
=========================================

_Overview_

* Preliminaries.
    * Admin.
    * Questions.
* Four questions about insertion sort.
* Lab.

Preliminaries
-------------

### Admin

* Writeup 6e and 8f.
  CSC 151.02 Writeup 28: Insertion Sort (Your Names)
* Note: The next time we have a fire alarm during a quiz, I'm not going to
  use the "everyone gets a ten" policy.
* Yes, I will teach you Anomia at some point if you'd like.  Maybe during
  a Monday study break.
* Upcoming extra credit opportunities:
    * Tuesday, November 26, 4:15 p.m., JRC 209  a gaming event with the 
      game [d0x3d!]   Popcorn will be served.
    * Any self-care week activity during purgatory week.
    * _One Grinnell_ rally on December 4 at 4pm.

Three questions about insertion sort
------------------------------------

* What is the key idea in insertion sort?
    * Repeately insert an element into the correct place in an already sorted list
* How does insertion sort differ in lists and vectors?
    * In vectors, we have to shove things over to make room.
    * And we're mutating the vector

Let's think about this in English.
 
     vec: vector we're sorting
     boundary: end of the sorted region
     val: the val we're inserting
     pos: position we're shifting from

     Initialization: set pos to immediately left of the boundary
     If the value at pos is less than the value we're inserting, 
         Put value at pos+1
     Otherwise, 
         shift the value at pos right one spot
         Recurse at pos-1

* Why do we provide you with three different kinds of list-based insertion 
  sort (and four kinds of insertion sort)?
     * One for numbers
     * One more general and one for keyed - different types
     * One for vectors

Lab
---