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

Crew Quest

Crew Quest: Card sorter
// Selection sort and sorted()
⏱ about 15 min

Crew Quest: Card sorter

The crew holds a sorting challenge with paper cards. Each card has a number from 1 to 20.

Rocket sorts with selection sort. Raven keeps two tallies: one for comparisons, one for swaps.

"Ten comparisons, three swaps!" she reports. "What do you notice if we start with the cards already in order?"

"The comparisons stay the same," Rocket says. "But the swaps go to zero!"

Nova cheers. "Here is a hint for the next round. Try the cards in reverse order."

  1. Selection sort finds the smallest unsorted item and swaps it into place.
  2. For n items it needs n - 1 passes.
  3. It always makes the same number of comparisons for the same number of items.
  4. sorted() makes a new list. .sort() changes the list itself.
  5. Sort once, then binary search as many times as you like.
◇ CARD SORTER
Write five different numbers on five paper cards. Mix them up in a row.
One person sorts with selection sort, one pass at a time.
The other person tallies every comparison and every real swap.
Try again with the cards already sorted, then in reverse order.
Compare the tallies. Which number never changed?
For a grown-up
For five cards, the comparison tally should be 10 every time. If it is different, count the cards looked at in each pass together.
RECAP QUESTION
  • Read the question.
  • Tap your answer.
Which Python tool sorts a list without changing the original?
Bonus recap statementTrue or false?
Selection sort needs 4 passes for 5 cards.?
A sorted list needs 0 comparisons.?
sorted() keeps the original list.?
Sort once, then search many times.?
WHY THIS EXERCISEThese are the four big ideas of sorting week.
How many comparisons for 5 cards?
How many real swaps to sort 1, 2, 3, 4?
What is the first item of sorted([8, 3, 5])?

Quest complete! Next week we split, sort and merge with merge sort.

← Friday