Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The problem of sorting.
• Writing sorting algorithms.
• Examples: Insertion, selection, etc.
• Formalizing the problem.

Preliminaries

Admin

• Continue partners.
• I will continue to bring you food (or food-like substances) until I am caught up on grading.
  
  • Today: Candy

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Review Sessions
  • Wednesday at 8pm in CS commons with Evan
  • Thursday at 10 am with SamR
  • Thursday at 8pm in CS commons with Alex

Upcoming Work:

• Reading for Wednesday: Sorting
• Projects due TONIGHT.
• Exam 4 distributed (as draft). Due next Tuesday.
• Official distribution of exam 4 tomorrow.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Thursday's CS Extra on STEM for the Blind. 4:15 p.m. in Science 3821. Food in the commons beforehand.
• Thursday, May 5, 8pm, the Science of Substances.
• Finals week's Inside Grinnell. Tuesday, May 17 at noon in JRC 101. The College Budget. Food served.
• Town Hall Thursday, Unpopular Identities. 11 a.m. and some other time.

Peer

• Flute Ensemble, Thursday, 7:30, Bucksbaum Gallery.
• Rushdie's East/West, May 6/7 at 7:30 p.m. No tickets necessary.
• Humans of Grinnell College on Facebook.

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.
  Just show up; you don't need to sign up.
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Bollywood, Fridays, 7:30-8:30, Younker
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Questions

Will the representative values be in the names of the images?

Yes,

I can't create the tar/zip file. What do I do?

Just attach all of the files to the message.

How much documentation for the helpers?

4Ps would be nice.

What if I've written 26 nearly-identical procedures?

You can write ;;; "See above"

If it's not important what the procedure returns, because, say, we've called a GIMP procedure, what should we do?

    ;;; Produces:
    ;;;   [Nothing of import]

How should we deal with the images we are copying and pasting?

Put them in a folder on your desktop. Email me the name of that folder and a note that "Sam, I give you permission to make that folder accessible." I'll fix things.

Do we have to document internal helper procedures from a named let or letrec or whatever?

No, but one line is often nice.

Document?

Yes. In ways that you think are clear.

The problem of sorting

Given a collection of values, put them in order.

• Order students by last name.
• Order movies by average rotten tomatoes rating.
• Dance moves by complexity.
• Books by title.
• Titular head movies by number of groans they elicit.

As computer scientists, we want to think about

• How we formally specify what it means to "sort" or "order" a collection?
  • Six-P's (or at least the first four)
• How do write a good sorting algorithm?
• How do we decide whether one sorting algorithm is better than another?
• How are we confident that our sorting algorithm is correct?

Designing a sorting algorithm

Think about writing a sort procedure in Scheme. What inputs would you have? What outputs would you have?

Group 1

• Input 1: The list to sort.
• Input 2: A binary comparator that lets us determine the order of two values.
• Output: A list

Group 2

• Input 1: The vector to sort.
• Input 2: A binary comparator that lets us determine the order of
• Output: None; we've changed the vector in place

Notes

• Comparator is important.
• We will look at vectors.

Writing sorting algorithms

We are going to sort 8 of you alphabetically by name. We already know how to compare things alphabetically. How do we get these eight people in order?

Strategy 1: TCNC Sort (aka Bubble Sort)

• Compare elements at positions 1 and 2. Swap if out of order.
• Compare elements at positions 2 and 3. Swap if out of order.
• ...
• Compare elements at positions N and N-1. Swap if out of order.
• Do it all over again
• And again
• And again
• Until you don't make any swaps.

Strategy 2: EHRB Sort

• Compare elements at positions 0 and 1. If not in order, shove the larger one to the end.
• Keep goiing.

Will it work? It looks like it. Will it be faster? It's hard to tell.

• Compare elements at position

Strategy 3: Selection Sort

• Put the smallest thing in position 0
• Put the next smallest thing in position 1 ...

Strategy 4: TFATP Sort

• Divide in half, small and large
• Recurse on each half

Formalizing the problem