CSC151.02 2013F, Class 46: Introduction to Sorting
==================================================

_Overview_

* Preliminaries.
    * Admin.
    * Questions on the project.
* The problem of sorting.
* Writing sorting algorithms.
* Examples.
* Formalizing the problem.

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

### Admin

* Welcome to any prospectives visiting with us today!
* There is no lab writeup for today.
  * There is, however, a quiz today.
  * And a reading for tomorrow.
* We have added an 11 am section of 161.  However, only 18 people have no conflicts
  at that time.  If you are taking 161 and can switch to 11, I would encourage you
  to do so during add/drop period.
* I may be sending out more grades tonight.
* Note: When grading lab writeups, I
    * Look in the folder where I file writeups when I arrive
    * Search in my mailbox for all the mail meeting the title of the lab
    * Search in my mailbox for all mail from people who don't seem to have
      submitted the lab
    * If I don't find your lab writeup after all of that, I have to assume
      that you have not submitted it.
    * So it really helps if you follow the naming conventions
* Upcoming extra credit opportunities:
    * "Data Sovreignty: The Challenge of Geolocating Data in the Cloud",
      November 25, 4:15 JRC 101
    * Showing of "Gold Fever" by Andrew Shurburne '01 or so, 7:00 p.m.
      Monday, November 25, ARH 302
    * Tuesday, November 26, 4:15 p.m., JRC 209  a gaming event with the 
      game [d0x3d!]   Popcorn will be served.
    * Any self-care week event during what I refer to as purgatory week.

### Questions on the Project

* Yes, you have a different due date than the other section.  Tuesday after
  Turkey break.
* Yes, you can apply the notes I gave you.
* No, you don't have to cite ideas.


The problem of sorting
----------------------

* Goal: To put things in order.

Writing sorting algorithms
--------------------------

* Yay!  A class exercise.
* Attempt it by hand
* Attempt to formalize
* Attempt to verify
* Attempt to turn into code

Examples
--------

* Letter sort - Bucket Sort [3 groups]
    * Find all of the A's
        * Then sort all of the A's.
    * Find all the B's
        * Then sort all of the B's.
    * For the recursive sorts, we use the next positions
    * ...
    * This can be relatively fast, if implemened correctly.
    * Need a way to break into categories.
* Bubble sort [3 groups]
    * Go through the list once, swapping out of order elements
    * Do it again and again and again ...
    * Sam's least favorite sorting algorithm
* Insertion sort [5 groups]
    * One by one, take cards from the original list and put them in
      "the correct place" in the second list
* "Binary sort"
    * Split the deck into two halves, small and large
    * Sort each half
    * Shove 'em back together
* Selection sort [1 group]
    * Repeatedly
        * Find the smallest remaining value
        * Add it to a new list
* Permutation sort
    * Make every permutation of the list
    * Decide which one is sorted

How would you choose which one to implement?

* Most efficient
    * Bucket, then "Binary" (Quicksort)
* Easiest to get right
    * Bubble
    * Selection
* Not bubble sort, because Sam will fail you

Formalizing the problem
-----------------------