← Back to course
Python 11-12 / Week 09 / Mission Quest
6/6
Week 09 · Sorting

Mission Quest

Mission Quest: Sort a hand both ways
// Selection and insertion sort; count the work
⏱ about 30 min

Saturday: Mission Quest: Sort a Hand Both Ways

On Saturday the crew brings a deck of number cards to the maker space. Comet deals five cards face up: 42, 18, 65, 7, 30.

"Race you," she says to Wren. "I will use insertion sort. You use selection sort."

Wren shakes his head and picks up a tally sheet. "What does the evidence say? Speed of hands is not the point. Count your moves instead."

Nova projects two tally boxes, one labeled swaps and one labeled shifts. "How can I help?" she asks. "Every time a card moves, make a mark."

Comet hands you the deck. "Lead programmer, run the race at home."

◇ SORT A HAND BOTH WAYS
You need: a deck of playing cards or ten paper slips with numbers on them, and a tally sheet.
1. Deal five cards face up in a row. Write the starting order down.
2. Selection sort: find the smallest card left and swap it into the next place. A family member tallies each swap that moves two cards.
3. Deal the same five cards in the same starting order.
4. Insertion sort: take the next card and slide larger cards one place right to make room. Your family member tallies each one-place shift.
5. Swap roles and try a new hand. Then try a hand that is already in order. Which way needs fewer moves?
For a grown-up
Selection sort finds the smallest card and swaps it into place. Insertion sort slides each new card into the cards already sorted.
There is no right answer to "which is better". Ask your learner which hands made each method look good.

Wren checks the first hand with a program that counts the moves the way your family member tallied them. Made-up data from the FieldSim story.

# count_moves.py


def selection_swaps(nums):
    """Selection sort; counts swaps that move two different cards."""
    swaps = 0
    for i in range(len(nums) - 1):
        smallest = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[smallest]:
                smallest = j
        if smallest != i:
            nums[i], nums[smallest] = nums[smallest], nums[i]
            swaps += 1
    return swaps


def insertion_shifts(nums):
    """Insertion sort; counts one-place shifts."""
    shifts = 0
    for i in range(1, len(nums)):
        current = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > current:
            nums[j + 1] = nums[j]
            j -= 1
            shifts += 1
        nums[j + 1] = current
    return shifts


print("swaps", selection_swaps([42, 18, 65, 7, 30]))
print("shifts", insertion_shifts([42, 18, 65, 7, 30]))
print("swaps", selection_swaps([7, 18, 30, 42, 65]))
print("shifts", insertion_shifts([7, 18, 30, 42, 65]))
swaps 2
shifts 6
swaps 0
shifts 0
WEEK 9 RECAP
  • Read the question.
  • Tap your answer.
For 42, 18, 65, 7, 30, which method moved cards more times?
Which sort finds the smallest item left on every pass?
Two samples weigh 30 g. A stable sort keeps them...

Excellent sorting this week. Next week the crew meets functions that call themselves, and a sort that splits the list in half.

← Friday