CSC151.01 2014F, Class 48: An Introduction to Sorting

Overview

Preliminaries

Have an terrific Thanksgiving. I hope that you have much to be thankful for. And please take care to be safe.
No review sessions this week.
We are doing algorithm design today.
- You learn algorithm design better by trying than by reading/listening.
- You learn better if you design the algorithm before thinking about how to express it in a programming language.
- So today is an "away from computer" day.

Karan's radio show 11pm Thursday nights on KDIC (not this week)
Evan's radio show 5pm Friday nights on KDIC (not this week)
Donna's radio show Sunday midnight on KDIC
Noteworthy at the Dance performance (Once Upon a Time, Splintered), December 4 and 5 in Flanagan
One acts, December 5 and 6 in Roberts

Given a list that's organized (e.g., alphabetically by name, numerically by Dewey Decimal number) look in the middle and figure out what half your element is on. Then run the element again on that half.
Slight corrections to the above:
- In the most general version, we need a way to determine how it's organized.
- If we see the element when we look in the middle, STOP!
- If you run out of elements, issue an error (either -1 or #f or an error)
- (Until corrected, we had "do it again and again" rather than a clear recursive approach.)
- Clarification: What if the list can't be split in half (or has no "middle"? Answer: Look next to the half (round down) E.g., if there are 16 things, we treat the eighth thing (position 7) as the middle.
- This only works on vectors. It's a PITN to look for the middle element of a list.
Note: We do not have anything more efficient for lists than looking at them one at a time.

Not down.