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!