Selection Sort

PG: Scrap. Scrap all. 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?

BH: Maybe insertion sort? It's more useful.

MF: I said keep, but I find these pages to be almost to much, and I want to review them.

One of the most commonly used sorts is called a selection sort. Here's how it works:

  1. Explore the selection sort before writing any code. With your class, stand up and form a line. Then, follow the selection sort process to put everyone in sorted, alphabetical order by first name.
  2. How is a selection sort an example of recursion? What is the base case?
AC suggestion: give opportunity to write sort NOW instead of waiting until after the helper functions are developed. Leaving as is for now.

To write a selection sort block in Snap!, you'll need code for a base case, and code that follows the steps of the selection sort.

  1. Write the earliest in block. For names, this returns the first name alphabetically in a list:
    {Emma, Olivia, Sophia, Isabella, Ava, Mia, Emily, Abigail} earliest in(list{Emma, Olivia, Sophia, Isabella, Ava, Mia, Emily, Abigail}) reporting Abigail
    2. ST-4/12/18 Tim Matthies Piazza request for visuals here in #4 and #5.
  2. Write code that finds the index of the earliest item. This value is 8 for the list of names above. (You may not need this step, depending on your algorithm. See if you can do the next step without it.)
  3. Need to correct link after new U5 labs are finished. --MF, 3/29/19
    You may find some of your work in Unit 5 Lab 1 Page 2: Analyzing and Improving Searches helpful.
    Write code that creates a new list with the earliest item deleted. There is more than one way to do this!
  4. Build the recursive reporter selection sort.
    selection sort(list{Emma, Olivia, Sophia, Isabella, Ava, Mia, Emily, Abigail}) reporting {Abigail, Ava, Emily, Emma, Isabella, Mia, Olivia, Sophia}
  5. How many times does selection sort call itself?
"U8L2-SelSort"save your work as U7L2-SelSort
Like recursive commands, recursive reporters can feel like magic, because part of the code tells the recursive reporter to call itself. Recursive reporters work because each time, the new call gives a smaller input to the same reporter, eventually reaching a base case. After the base case is reached, the final result is built up piece by piece as each call reports a value to its caller.
  1. This 2014 Popularity of Baby Names data file contains a large list of baby names from 2014. Import the data, then build an algorithm that returns an alphabetical list of all names starting with a given letter:
    names starting with(Z) reporting {....,Zacary, Zaccal, Zaccahaeus, Zaccheus, Zach, ...}
    2. ST-4/13/18: Tim Matthies at Piazza noticed that we need to give directions for how to import this data. It turns out that capturing the data from the link given, importing and cleaning it is completely non-trivial and I don't think we have done this before in the curriculum. I recommend we make the following (huge) starter file available where the names are isolated and listed in popularity order, devoid of gender and number fields.