Comet wraps yesterday's steps in a loop. "One pass for each place," she says, typing fast. "That is the whole sort."
Wren stops her before she runs it. "What does the evidence say? Let's print the list after every pass and check it against yesterday's cards."
Comet groans, then grins. "Fine. If the prints match the cards, I win."
Nova projects the four pass rows from Monday beside an empty output box. "How can I help?" she asks. "Watch i and smallest. They tell the whole story of each pass."
Comet passes you the keyboard. "Lead programmer, trace it with us."
The outer loop picks the place i to fill. The inner loop finds the smallest item from i to the end. Then one swap puts it in place i.
This is the function you will type into sorts.py tomorrow. The copy below adds one print, so you can see each pass.
def selection_sort(nums):
for i in range(len(nums) - 1):
smallest = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i] # selection_passes.py
# A copy of selection_sort that prints the list after each pass.
def selection_passes(nums):
for i in range(len(nums) - 1):
smallest = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i]
print("pass", i + 1, nums)
selection_passes([42, 18, 65, 7, 30]) | i | Part searched | smallest (index) | Swap | List after the pass |
|---|---|---|---|---|
| 0 | 42, 18, 65, 7, 30 | 3 (value 7) | places 0 and 3 | [7, 18, 65, 42, 30] |
| 1 | 18, 65, 42, 30 | 1 (value 18) | place 1 with itself | [7, 18, 65, 42, 30] |
| 2 | 65, 42, 30 | 4 (value 30) | places 2 and 4 | [7, 18, 30, 42, 65] |
| 3 | 42, 65 | 3 (value 42) | place 3 with itself | [7, 18, 30, 42, 65] |
pass 1 [7, 18, 65, 42, 30] pass 2 [7, 18, 65, 42, 30] pass 3 [7, 18, 30, 42, 65] pass 4 [7, 18, 30, 42, 65]
The < in selection_sort works on strings as well. Run this and see the order it gives. Made-up data from the FieldSim story.
# sort_kinds.py
from field_data import CATALOG
def selection_sort(nums):
for i in range(len(nums) - 1):
smallest = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i]
kinds = []
for label, kind, grams in CATALOG:
kinds.append(kind)
selection_sort(kinds)
print(kinds[0])
print(kinds[-1]) basalt slate
This is the run for step 3. There is no traceback, but the list is wrong.
# indent_oops.py
def selection_oops(nums):
for i in range(len(nums) - 1):
smallest = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i]
nums = [42, 18, 65, 7, 30]
selection_oops(nums)
print(nums) [30, 7, 18, 42, 65]
| Statement | True or false? |
|---|---|
| The inner loop finds the smallest item; the swap comes after it. | ? |
| selection_sort gives back a new sorted list. | ? |
| The same selection_sort can sort strings into A to Z order. | ? |
| Indentation decides which loop a line belongs to. | ? |
Four passes, four rows, every one checked. Tomorrow you build sorts.py and count every comparison.