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

_Overview_

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

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

### Admin

* New partners!
* Review session tonight at 7pm.
* 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.

### 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 (Afternoon Section)

* Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

#### Miscellaneous

* Donate to UNICEF or Red Cross to support recovery in Nepal.
  Read the campus memo for more info.

### Other Good Things (no extra credit)

* Donate even more to UNICEF or Red Cross or other organizations

### 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.
* Comparing lists to trees
    * cons -> node
    * pair? -> node?
    * null -> nil
    * null? -> nil?
    * car cdr -> root-value, left-subtree, right-subtree
* You do not need to cite the initial code file.

### Notes on the Project

* Yes, separate helpers are a good idea for development.  4Ps suffice,
  as does reasonable shorthand.
        ;;; (fishy! image n)
        ;;;    Draws the nth fish on the image.
* 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!
* One folder, one email

### Questions

* When is the final?
    * Tuesday or Wednesday of finals' week
    * 9am or 2pm
* We will talk about the final a week from Wednesday.

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

* Binary search - Searches an ordered non-empty vector for an 
  entry (entries are often lists)
* So ... we want a way to put vectors in order.

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

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

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