CSC151 2010S, Class 47: Introduction to Sorting

Overview:
* The problem of sorting.
* Writing sorting algorithms.
* Examples: Insertion, selection, etc.
* Formalizing the problem.

Admin:
* Reminder: One more day to register for classes!
* Reading for Friday: Sorting.
* I will not be in class on Friday
  Prof. Weinman and a guest will be here.
* Note: I do plan to release tentative grades 
  and such during week 14
* EC for Osgood convocation tomorrow.
  * Warning, it's a PBK convo!
* EC for Friday's CS Extra Table (Science 3821). 
  I need a headcount! 3

Sorting:
* Given a collection of values
  Criterion for ordering pairs of values
* Goal: Put them in order from smallest to
  largest according to the criterion

E.g., a collection of students
* Order them by grade (from least to most or vice versa)
* By name (alphabetically)
* By class year
* By mailbox number (or zip code or ...)

Technique one: Insertion Sort
* Two groups of people:
  * Those we haven't processsed yet
  * Those who are already in order
* Repeatedly grab one unprocessed person
* Compare that person to each of the people
  in the ordered list
  * If that person precedes the next person
    stop
  * Otherwise, move on to the next person

Technique two: Insertion Sort with Binary Search
* Two groups of people
  * Unprocessed
  * Sorted
* Repeatedly grab one unprocessed person
  * Find the appropriate place for that person
    using binary search

Technique three: Selection Sort
* Repeatedly
  * Find the "largest" element of the group
  * Remove it and put to the side

Technique threeD: Selection Sort from both ends

Technique four: Bubble Sort
* Repeatedly swap things that are out of order
* Never use bubble sort!