Sorting a List

PG: Scrap. Scrap all [in this lab]. Two reasons. (1) While sorting algorithms is an important and traditional CS topic, it's not obvious to me why they have any important role in an attract-them-in course. These are TiF for interested kids. (2) If our reason for this unit is to teach recursion, sorting is a distraction, and harder than we need to be. If anything at all, it's a culmination, not a start. I'd be happier showing kids how to march down a list and act on it. With HoFs or recursion. Power and utility. That's currently in Lab 4. Maybe earlier even than this unit?

See also the cut U3 version:
These are the top 8 baby girl names in the USA in 2014.
BH suggestion: change order of names so Abigail isn't last; could cause confusion in describing sort algorithms. Leaving as is, since it affects multiple graphics, but a good fix.

Suppose we have a list names that we want to sort in alphabetical (ascending) order:

These could be numbers instead of names or anything that can be compared and ordered. Numbers and words often need to be sorted in the same list.
Eight names → Eight names, sorted

Kill the sentence about numbers and words; numbers don't sort numerically if you do a lexicographic sort, so mixing the two is tricky. --bh
    Try to describe the algorithm in enough detail so that someone else could use your description to sort a list.
  1. Design a recursive algorithm for sorting the names.
    • First consider your general strategy; how would you sort a group of names, step-by-step.
    • Then consider how you would tell a computer, which is not as smart as you and can only perform specific procedures, how to sort a list.
  2. Now build your algorithm: a sort reporter takes a list as input and outputs a new list of the same elements in alphabetical order. Test your algorithm using both names and numbers.
    3. Comparing numbers and strings can be done using the same blocks, so your sorting algorithm should work equally well for names and numbers.
    (Abigail)<(Ava) reporting true (7)<(3) reporting false
  3. Share your sorting algorithms. Describe some similarities and differences between different sorting algorithms.

There are many different algorithms to sort a list. Sorting algorithms give the same result, but the code and efficiency can vary greatly from one algorithm to another. The next two pages highlight two frequently used sorting algorithms.