Binary search needs sorted data, and the catalog is not sorted. Comet writes five sample weights on index cards and drops them on the bench: 42, 18, 65, 7, 30.
"Sorting is easy," she says, and shuffles them into order in two seconds. "Done. Next problem."
Wren smiles and holds up his clipboard. "What does the evidence say? You did it, but you cannot say how. A program needs steps it can repeat."
Nova projects the five cards in a row, with an empty box at the far left. "How can I help?" she asks. "Find the smallest card left. Move it to the next empty place. Repeat."
Comet slides the cards back into a row. "Lead programmer, talk me through it, one card at a time."
Selection sort repeatedly picks the smallest item from the unsorted part of the list and swaps it into its final place.
Take the cards 42, 18, 65, 7 and 30. The smallest is 7, so 7 swaps with 42, the card in the first place. Now the first place is final. Then repeat on the four cards after it.
Here is the first step in code. Read it and predict before you run it.
# smallest.py
# Made-up data from the FieldSim story: five sample weights.
nums = [42, 18, 65, 7, 30]
start = 0
smallest = start
for j in range(start + 1, len(nums)):
if nums[j] < nums[smallest]:
smallest = j
print("smallest at", smallest, "value", nums[smallest])
nums[start], nums[smallest] = nums[smallest], nums[start]
print(nums) smallest at 3 value 7 [7, 18, 65, 42, 30]
| Pass | Smallest left | Swap | Cards after the pass |
|---|---|---|---|
| 1 | 7 | 7 and 42 | 7, 18, 65, 42, 30 |
| 2 | 18 | 18 with itself | 7, 18, 65, 42, 30 |
| 3 | 30 | 30 and 65 | 7, 18, 30, 42, 65 |
| 4 | 42 | 42 with itself | 7, 18, 30, 42, 65 |
Comet first wrote the swap as two separate lines. Predict what goes wrong.
# bad_swap.py nums = [42, 18, 65, 7, 30] nums[0] = nums[3] nums[3] = nums[0] print(nums)
[7, 18, 65, 7, 30]
Python can also swap two items in one line, as smallest.py does: nums[0], nums[3] = nums[3], nums[0]. Try it in step 3 below and see that nothing is lost.
This is the run for step 2, with start = 1.
smallest at 3 value 7 [42, 7, 65, 18, 30]
| Statement | True or false? |
|---|---|
| After each selection sort pass, one more item is in its final place. | ? |
| Selection sort swaps every pair of neighbors that is out of order. | ? |
| nums[0] = nums[3] then nums[3] = nums[0] swaps two items correctly. | ? |
| Five cards need at most four passes. | ? |
You turned "just sort it" into steps a program can repeat. Tomorrow you write selection sort as a function.