Selection Sort

One commonly used sorting algorithm is called selection sort. Here's how it works:

(Don't take the word "step" too literally; you'll probably see when you write the code that at least steps 3-4 are in a single report block.)

  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 order by month and day of birth (for example, 10/4).
  2. How is a selection sort an example of recursion? What is the base case?
  3. Open your project "U3L1-ContactList"; save it as "U3L2-ContactList".
    We want to sort contact list by name, but we're going to start with a simpler problem: sorting a list of numbers or words, so that you can use less than to compare two items. On the next page you'll modify your program to sort the contact list.
  4. If you'd like to write the sort block with no help at all, do it now. Otherwise you can click here.
To write a sort block in Snap!, you'll need code for a base case, and code that follows the steps of the selection sort.

The less than block will compare words, using alphabetical order, not just numbers.
  1. Write the earliest in block. For names, this returns the first name alphabetically in a list:
    Eight names Earliest name for alphabetical order
    This can be done in several ways. Click here for one of them.
    1. Write the min block that takes two inputs and reports whichever is smaller. (You've done this before, but it's probably quicker to do it again than to find it in some earlier project and import it.)
    2. Write the earliest block using combine.
  2. The selection sort algorithm says to find the smallest item in a list, recursively sort the remaining items, and stick the smallest item in front of the result. Write a block remove ( ) from ( ) that reports a list that's a copy of its second input, but with its first input removed.
    remove (what) from (list and she told me what to say) -> {and, she, told, me, to, say}
    You can do this using keep if you assume that there are no equal items in the list. That's fine for now, although a correct sorting algorithm will keep all duplicate items in the result.
    You can write a recursive version that removes only the first copy of the word from the list.
    You might be tempted to use the command replace item ( ) of ( ) with ( ) or delete ( ) from ( ) in this problem, but your sort block should report a new sorted version of the list, without changing the original list. Sometimes it's okay to modify the original list, but sometimes it isn't, so go for the most generally useful solution.
  3. Build the recursive reporter sort.
    Result of a selection sort on eight names
  4. How many times does sort call itself?
Save Your Work
  1. This 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:
    Alphabetical list of names starting with Z
    To import the data:
    1. Make a global variable baby names. Right-click on the variable in the palette to see this menu:
      context menu with "transient" checkbox
      Check the "transient" checkbox in that menu. (This tells Snap! not to save the value of the variable when saving the project, because the value is too big to fit in a saved project.) Leave the watcher on the stage so you can see the effect of each of the following steps.
    2. Get the names from the web:
      set (baby names) to (http:// [bjc.edc.org/June2020bjc2/bjc-r/cur/programming/3-lists/2-sorting/yob2014.txt])
      Here's that text in a form you can copy and paste:
      bjc.edc.org/June2020bjc2/bjc-r/cur/programming/3-lists/2-sorting/yob2014.txt
    3. Turn the multi-line text into a list of lines:
      set (baby names) to (split (baby names) by (line))
    4. In database terminology, each item of this list is a record. Within each record, there are three fields separated by commas: name, sex, and the number of babies given that name in 2014. Turn each record into a list of the fields:
      set (baby names) to (map (split ( ) by (,)) over (baby names))
      That's a comma in the second input slot of split.
    5. Talk with Your Partner Why is map used in part (d) but not in part (c)?
    6. Note: Repeatedly changing the value of a variable with set isn't the most beautiful style, although it's great for explaining the steps. Over time, try to develop the habit of doing this instead:
      set (baby names) to (map (split ( ) by (,)) over (map (split (http:// [bjc.edc.org/June2020bjc2/bjc-r/cur/programming/3-lists/2-sorting/yob2014.txt] by (line))))
    7. Now write names starting with.