Comet wants sorting in FieldSim for good. "One module, like search.py," she says. "Selection sort, plus whatever else we need."
Wren adds two lines to her list. "What does the evidence say? We will need to sort samples, not just numbers. And I want to know how much work each sort does."
Nova projects the ten catalog weights with a small counter above them, still at zero. "How can I help?" she asks. "Count every comparison. Then the numbers can argue for you."
Comet cracks her knuckles. "Lead programmer, you type sorts.py. Wren counts. I predict."
Stage 1. Each run of sorts.py shows nothing, because the file only defines functions. No traceback means no syntax errors.
# sorts.py
# Selection sort and insertion sort (week 9). Both sort the list in place.
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] Stage 2: insertion_sort().
def insertion_sort(nums):
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
nums[j + 1] = current Stage 3: sort_by_grams(), the same steps on Sample objects, comparing their grams.
def sort_by_grams(samples):
"""Insertion sort on Sample objects, lightest first."""
for i in range(1, len(samples)):
current = samples[i]
j = i - 1
while j >= 0 and samples[j].grams > current.grams:
samples[j + 1] = samples[j]
j -= 1
samples[j + 1] = current Now sort_demo.py sorts two copies of the catalog grams, one with each sort. Made-up data from the FieldSim story.
# sort_demo.py
from field_data import CATALOG
from sorts import insertion_sort, selection_sort
grams = []
for label, kind, g in CATALOG:
grams.append(g)
a = list(grams)
b = list(grams)
selection_sort(a)
insertion_sort(b)
print(grams)
print(a)
print(a == b) [42, 18, 65, 7, 30, 51, 12, 88, 25, 39] [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] True
A statement execution count shows how many times a line runs. This copy of selection sort counts each time the inner loop compares two numbers.
# count_selection.py
# A copy of selection_sort that counts comparisons.
from field_data import CATALOG
def selection_count(nums):
"""Sorts nums in place and gives back the number of comparisons."""
comparisons = 0
for i in range(len(nums) - 1):
smallest = i
for j in range(i + 1, len(nums)):
comparisons += 1
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i]
return comparisons
grams = []
for label, kind, g in CATALOG:
grams.append(g)
print(selection_count(grams))
print(grams) 45 [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
Here is the run with a second print(selection_count(grams)) added at the end.
45 [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] 45
Break one thing on purpose. Save a copy of sorts.py as sorts_w9.py first. Then, in sorts.py, change range(i + 1, len(nums)) to range(i + 1, len(nums) + 1). Run sort_demo.py and read the traceback from the bottom.
Traceback (most recent call last):
File "sort_demo.py", line 10, in <module>
selection_sort(a)
~~~~~~~~~~~~~~^^^
File "sorts.py", line 9, in selection_sort
if nums[j] < nums[smallest]:
~~~~^^^
IndexError: list index out of range Change len(nums) + 1 back to len(nums), or copy the line from sorts_w9.py, and run sort_demo.py again.
sorts.py is done, and you counted the work. Tomorrow you trace insertion sort and see a very different count.