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

Wednesday

Selection sort in Python
// Selection sort and sorted()
⏱ about 15 min

Wednesday: Selection sort in Python

Rocket wants the computer to sort the IDs. He writes a loop to find the smallest. Then he gets stuck.

"How do I make two items trade places?" he asks. "If I copy one over the other, I lose it!"

Raven picks up a cup in each hand. "What do you notice when I trade these?"

"You have to move both at the same time," Rocket says.

Nova hums. "Here is a hint. Python can do both moves in one line."

Swapping in one line

a = 4
b = 9
a, b = b, a
print(a, b)
Output:
9 4

The right side is worked out first, using the old values. Then both new values are stored at once.

The selection sort function

This sort has a loop inside a loop. The outer loop picks the spot to fill. The inner loop finds the smallest card for it.

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print(items)
    return items

selection_sort([7, 3, 9, 1, 5])
Output:
[1, 3, 9, 7, 5]
[1, 3, 9, 7, 5]
[1, 3, 5, 7, 9]
[1, 3, 5, 7, 9]
  • i is the spot being filled in this pass.
  • smallest remembers the spot of the smallest card found so far.
  • The inner loop compares each later card with the smallest so far.
  • After the inner loop, one swap puts the smallest card in spot i.
RUN SELECTION_SORT([4, 2, 5, 1]) IN YOUR HEAD.
  • Read the question.
  • Tap your answer.
What does the first print show?
What does the last print show?
How many lines does selection_sort print for a list of 6 items?
WHY THIS EXERCISEThe outer loop runs n - 1 times, and each pass prints once.

Practice lab: sort four IDs

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print(items)
    return items

selection_sort([6, 2, 8, 4])
How many lines does the program print?
After the first pass, what number is in spot 0?
In the second pass, which number swaps with 6?
a is 1 and b is 2. After a, b = b, a, what is a?
CODE CHECK
  • Read the question.
  • Tap your answer.
At the start of each pass, what does smallest start as?
Why does the inner loop use range(i + 1, n)?
What does selection_sort([3, 1, 2]) print first?
StatementTrue or false?
The last line printed is [2, 4, 6, 8].?
The inner loop does the swapping.?
The outer loop runs n - 1 times.?
a, b = b, a uses the old values on the right side.?
WHY THIS EXERCISEThe inner loop finds. The swap line moves.
How many lines would selection_sort print for a list of 10 items?
WHY THIS EXERCISEThe outer loop runs n - 1 times, so 10 items print 9 lines.

Super work! You read a loop inside a loop. Tomorrow we let Python sort for us.

← Tuesday