Page 2: Selection Sort

Unit 8, Lab 6, Page 2

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

  • The earliest item might be the first name in alphabetical order, or the smallest number in a list.

    Step 1. In an unsorted list, find a way to select the item that should come earliest in the sort.

  • Step 2. Pull the selected item out of the list and place it in the first position.

  • Step 3. With the remaining items, use a selection sort to put them in order. If there are no remaining items, you’re done.

  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.

  1. How is a selection sort an example of recursion? What is the base case?

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

  1. 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.)

  1. Write code that creates a new list with the earliest item deleted. There is more than one way to do this!

  1. 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}

  1. How many times does selection sort call itself?

“U8L6-SelSort” Save your work as U8L6-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.

Take It Further…

  1. Assignment This starter project contains a large list of baby names from 2014, in popularity order. Load it, 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, ...}