← Back to course
Code Crew G5 / Week 08 / Monday
1/6
Week 08 · Sorting by hand

Monday

Smallest to the front
// Selection sort and sorted()
⏱ about 15 min

Monday: Smallest to the front

Binary search needs a sorted list, but new star IDs arrive all jumbled. Rocket lays five ID cards on the table: 7, 3, 9, 1, 5.

"I will just shuffle them around until they look right," he says, sliding cards everywhere.

Raven stops his hand gently. "What do you notice about where the smallest card belongs?"

"At the very front," Rocket says. "So find the smallest first?"

Nova draws a glowing line after the first spot. "Here is a hint. Once a card is in place, you never touch it again."

Selection sort

  1. Look at every card that is not sorted yet. Find the smallest.
  2. Swap it with the card in the first unsorted spot.
  3. That spot is now sorted. Move the line one spot to the right.
  4. Repeat until only one card is left. One card is always sorted.
PassSmallest foundCards after the pass
Start7, 3, 9, 1, 5
111, 3, 9, 7, 5 (1 swapped with 7)
231, 3, 9, 7, 5 (3 is already in place)
351, 3, 5, 7, 9 (5 swapped with 9)
471, 3, 5, 7, 9 (7 is already in place)

Five cards took 4 passes. The last card did not need a pass, because it was the only one left.

Sort 6, 2, 8, 4. Which card is the smallest in pass 1?
After pass 1 the cards are 2, 6, 8, 4. Which card is the smallest in pass 2?
SORT 6, 2, 8, 4 WITH SELECTION SORT. TAP THE CARD LISTS INTO ORDER.
  • Tap a card.
  • Then tap its spot.
1Start
2After pass 1
3After pass 2
4After pass 3
THINK ABOUT SELECTION SORT.
  • Read the question.
  • Tap your answer.
How many passes does selection sort need for 5 cards?

Practice lab: five more cards

Sort the cards 5, 1, 4, 2, 3 with selection sort. Pass 1 swaps 1 with 5, giving 1, 5, 4, 2, 3.

In pass 2, which card is the smallest unsorted card?
In pass 3, which card is the smallest unsorted card?
How many passes does this sort need?
How many passes would 9 cards need?
PASS CHECK
  • Read the question.
  • Tap your answer.
What are the cards after pass 2?
Which cards are sorted for good after pass 2?
Why is no pass 5 needed?
StatementTrue or false?
Pass 1 always finds the smallest card of all.?
Selection sort touches sorted cards again later.?
After pass 3, the cards are 1, 2, 3, 5, 4.?
Pass 4 swaps 4 and 5.?
WHY THIS EXERCISETracing each pass shows the sorted part grow from the left.
How many passes does selection sort need for 12 cards?
WHY THIS EXERCISEThe last card is in place once the other 11 are.

Great sorting! You found the smallest and moved it front, again and again. Tomorrow we count every comparison.