CSC151.01 2015S, Class 48: An Introduction to Sorting
=====================================================

* New partners!

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* The problem of sorting.
* Writing sorting algorithms.
* Examples of sorting algorithms.
* Formalizing the problem.

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

### Admin

* Review session tonight at 7pm.
* I continue to try to add office hours.
* Quiz 12 returned.  
    * If you have questions, go to the review session tonight (or 
      talk to me, or talk to a tutor, or email me)
* Today is another discussion-style day.
* Welcome to our prospective!

### Upcoming Work

* Projects due tomorrow night.  Read the instructions!
* Exam 4 assigned, due next Monday.
    * Prologue due Friday night!
* No lab writeup.
* Reading for Tuesday:
  [Sorting](../readings/sorting-reading.html)

### Extra Credit Opportunities

#### Academic 

* Toward an Embodied Liberal Arts, Tonight, 8pm, JRC 101
* PBK Convo, Wednesday.

#### Peer Support (Morning Section)

* KY's radio show, "We Think We're Funny", 9-10pm Mondays (TONIGHT).
  TBD.
* Julia's radio show, "The Hot Box".  Wednesday night/Thursday 
  morning 1:00-2:00 a.m.  
* Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

#### Miscellaneous

_None at the moment._

### Other Good Things (no extra credit)

_None at the moment._

### Notes on the Exam

* Electronic due Monday, printed due Tuesday.
    * Gives me time to try to get you grades sooner.
    * Experience shows most class have work due later in the week.
    * I will discuss extensions.
* Starts with a pre-set Racket file to make it easier for you and
  for me.
* Seven problems, as always.
* Four problems are on a new model of trees.
     * cons becomes node
     * pair? becomes node?
     * null becomes nil
     * null? becomes nil?
     * car and cdr become root-value, left-subtree, right-subtree

### Notes on the Project

* Yes, separate helpers are a good idea for development.  4Ps suffice,
  as does reasonable shorthand.
        ; (butterfly! image n)
        ;   Draws a really cool butterfly on the image, with
        ;   the wing shape depending on n.
* Make sure to review the requirements, including the rubric.
* Scaling is essential.  Stretching (switching aspect ratios) may be 
  needlessly difficult.  
    * If your images don't stretch, DOCUMENT IT!
    * If your images look better at certain aspect ratios, NOTE IT!
* You will not get comments back on your proposals.

### Questions

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

* Binary search!
    * Divide vectors into two sections, look in appropriate section
    * Vectors must be in order! (by key)
* Problem: If we have an unordered vector, how do we put things in
  order?  The problem of sorting!

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

* Let's think about some examples and how we'd do them by hand.

Examples: Insertion, selection, etc
-----------------------------------

Three sorting algoritms

* Move through the vector, swapping elements that
  are out of order (and again, and again, and again, and again)
* Create a new vector, repeatedly put the next element in the
  correct place in the new vector.  "Insertion sort"
* Create a new vector, repeatedly grab the largest remaining element
* Which is best?
    * Theoretically, these are essentially equivalent in terms of cost.
    * But some are better for certain inputs.

Key operations

* Repeat (and know when to stop, and repeat repetitions)
* Compare two elements
* Swap two elements

Improving

* Break it in half, sort each half
* Do compare and swap simltaneously
* Break into sections
  and put it at the end of the new vector.

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

        ;;; Procedure:
        ;;;   sort
        ;;; Parameters:
        ;;;   vec, vector
        ;;;   may-precede?, a binary predicate
        ;;;   get-key, a unary operation
        ;;; Purpose:
        ;;;   Create a new vector that contains the values in vec,
        ;;;   in order from smallest to largest.
        ;;; Produces:
        ;;;   sorted, a vector
        ;;; Postconditions:
        ;;;   See the preconditions for binary search.  The vector
        ;;;   should meet those preconditions.