CSC 151.01, Class 35: An introduction to sorting

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• The problem of sorting
• Writing sorting algorithms
• Some examples
• Formalizing the problem

Preliminaries

News / Etc.

• New partners!
• I should get responses to project proposals done by Friday.
• Upcoming schedule
  • Friday: Project time (plus quiz)
  • Monday and Wednesday: More sorting (labs)
  • Friday May 4: TBD
  • Monday May 7: Project presentations (5 min each)
  • Tuesday May 8: Exam 4 due
  • Wednesday: May 9: Debrief on class
  • Friday, May 11: Wrapup (required) + Review for final (optional)

Upcoming work

• No lab writeup.
• Flash Cards due TONIGHT at 9pm.
  • Optional.
  • Grade is percent of eight flashcard assignments you complete (capped at 100%).
• No reading for Friday.
• Quiz Friday: Searching (association lists, sequential search, binary search)
  • Sample question: Suppose our data have this form. Write a call to assoc (or binary-search) to extract this part of one datum.
  • Sample question: Interpret the following call to assoc; what results will you get?
  • Sample question: In the following call to binary-search, what values does the binary search procedure examine?
  • Sample question: Fill in the following template for assoc-all.

Extra credit (Academic/Artistic)

• Vance Byrd Book Talk Thursday at 4:15 pm, Burlilng 1st Floor Lounge

Extra credit (Peer)

• Thursday, April 26th, Noyce 2022: Mellon Mays Project introductions, 4:15 to 6:30 p.m.
• Dance Ensemble Thursday 7:30pm, Friday 7:30pm, Saturday 7:30pm, Sunday 2pm. Roberts. Tickets still left.
• Open Mike Thursday 9-11pm in Bob’s.
• Friday, 8pm, Main: Contra Dance

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Listen to KDIC Thursday at 7pm - Classic Rock. (60’s and 70’s)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Any Sexual Assault Awareness Month event.

Other good things

Questions

The problem of sorting

Quick review: What are the parameters to binary-search? What are the parameters to sort?

• (binary-search vec get-key may-precede? key)
  • vec is a vector of compound values (maybe lists, or vectors, or …?) organized according to may-precede?
  • get-key is a procedure that extracts a “key” from one entry in the vector. A key is the element of an entry that you use as you search; the kind of info that you’re searching for.
  • may-precede? relates to the keys, we used string-ci<=? for strings and <= for numbers and ….
    • may-precede? describes the ordering of the vector, which is important for more efficient searching.
  • key: What we’re looking fora
• (sort lst comparator)
  • lst is a list of values
  • comparator - a way to compare two values for order, a lot like the may-precede? in binary-search.
• Key differences
  • The sort works with lists, binary-search works with vectors.
    • To use binary-search on an unsorted vector, we’d need to do some converstion.
    • Alternately, we could write (or hope there exists) a sort for vectors.
  • There’s no get-key in sort. Why don’t we need it? Alternately, how would you sort '(("Rebelsky" "Samuel") ("Klinge" "Titus") ("Walker" "Henry") ...) by first name?a
    • We build the get-key into our comparator.
    • Not quite: (sort faculty (string-<=? (cadr p1) (cadr p2)))
    • (let ([first-name-<=? (lambda (p1 p2) (string<=? (cadr p1) (cadr p2)))]) (sort faculty first-name-<=?))
    • (sort faculty (lambda (p1 p2) (string-<=? (cadr p1) (cadr p2))))

How do we do binary search if the vector contains, say, only numbers? (That is, they aren’t really compound data.)

• The procedure binary-search still assumes that we have a get-key.
• Each value is its own key.
• get-key will be (lambda (x) x).

Writing sorting algorithms

Our goal: To come up with a strategy for sorting vectors that does not involve calling the built-in sort for lists.

• Note: One strategy for developing algorithms is to think about how you’d do it by hand.

OB+MS sort

• Set position to 0-
• Compare position 0 and position 1. If the value at position 0 may precede the value at position 1, do nothing.
• Go to the next position
• If the two are out of order, swap them and “jump back” to the previous position
• Note: We don’t back up when the position is 0.

We think this will work, but it will take a lot of time.

Insertion sort

• Divide the world into “stuff that’s sorted” and “stuff that’s not yet sorted”.
• Take the first thing in the not sorted, working from the left, find out where they belong
• Shift everyone down so that there’s room
• Do it all again

What do you think?

• Looks correct, but also slow.
• Bad: Always grab the shortest person, lots of shifting: Shift 0, shift 1, shift 2, shift 3, shift 4, ….
• Also bad: Always grab the tallest person, lots of comparsioni
• Approximately n*(n+1)/2 “steps” (comparison or shift)

Another algorithm: Selection sort

• Once again, divide into sorted and unsorted.
• Find the “smallest” unsorted.
• Put it at the front of unsorted.
• Do it again.
• Finding the smallest in a group of n things, takes about n steps.
• n + n-1 + n-2 + … +1. Another n*(n+1)/2 “steps” algorithm.

Here’s a question that lots of people face(d) when studying sorting: Can we do better than “about n*(n+1)/2 steps”?

Hmmm … binary search changed something that took n steps into something that took much fewer than n steps. (log n) steps, for the mathematically inclined.

• Binary search uses “divide and conquer”.
• Maybe we can use something similar for sorting.

Divide-and-conquer sorting

Idea number one: Just like insertion sort, except use binary search to find the position.

• Sam notes that you still have the high cost of shifting.
• Sam notes that if you have lists, looking in the middle is hard.

Idea number two: Find the median. Divide into things less than the median and greater than the median. Sort the two halves. Join ‘em together.

• Sam notes that it’s hard to find the median.
• Students ask “How do we write swap`?

(define vector-swap!
  (lambda (vec pos1 pos2)
    (let [(tmp1 (vector-ref vec pos1))
          (tmp2 (vector-ref vec pos2))]
      (vector-set! vec pos1 tmp2)
      (vector-set! vec pos2 tmp1))))

Idea number three: Divide in half. Sort each half. Then …?

• Sam notes that the last step is hard. But we’ve written it before.

Formalizing the problem