The catalog is a list of samples, not a list of numbers. Comet wants it in order, lightest first, so binary search can use it.
"Python already sorts lists," she says. "Why not just use that?"
Wren taps the catalog. "What does the evidence say? Two test samples weigh exactly 30 g. If we sort by weight, which one comes first afterwards?"
Nova projects two cards with the same weight, labeled T1 and T2, side by side. "How can I help?" she asks. "Watch whether equal items keep their order."
Comet pushes the cards toward you. "Lead programmer, trace it on paper first."
sort_by_grams() in your sorts.py is insertion sort on Sample objects. It compares samples[j].grams with current.grams, and moves whole Sample objects. Made-up data from the FieldSim story.
# catalog_sort.py
from field_data import CATALOG
from sample import Sample
from sorts import sort_by_grams
samples = []
for label, kind, grams in CATALOG:
samples.append(Sample(label, kind, grams))
sort_by_grams(samples)
for s in samples:
print(s.label, s.kind, s.grams) S04 mica 7 S07 slate 12 S02 quartz 18 S09 chalk 25 S05 granite 30 S10 sandstone 39 S01 basalt 42 S06 shale 51 S03 clay 65 S08 flint 88
Python has its own sorts too. The method list.sort() sorts a list in place. The function sorted() gives back a new sorted list and leaves the old one as it was.
# own_sorts.py grams = [42, 18, 65, 7, 30] new = sorted(grams) print(new) print(grams) result = grams.sort() print(grams) print(result)
[7, 18, 30, 42, 65] [42, 18, 65, 7, 30] [7, 18, 30, 42, 65] None
A sort is stable when items with equal keys keep their order. Python's own sort is stable.
Here T1 and T2 both weigh 30 g, and T1 comes first. The program sorts one copy with sort_by_grams and one with a selection sort copy that compares grams.
# stable.py
from sample import Sample
from sorts import sort_by_grams
def selection_by_grams(samples):
"""A copy of selection_sort that compares .grams."""
for i in range(len(samples) - 1):
smallest = i
for j in range(i + 1, len(samples)):
if samples[j].grams < samples[smallest].grams:
smallest = j
samples[i], samples[smallest] = samples[smallest], samples[i]
def labels(samples):
result = []
for s in samples:
result.append(s.label)
return result
tests = [Sample("T1", "clay", 30), Sample("T2", "shale", 30), Sample("T3", "mica", 10)]
a = list(tests)
b = list(tests)
sort_by_grams(a)
selection_by_grams(b)
print(labels(a))
print(labels(b)) | Pass of selection_by_grams | Smallest left | Swap | Order after |
|---|---|---|---|
| 1 | T3 (10 g) | T3 and T1 | T3, T2, T1 |
| 2 | T2 (30 g); T1 is not smaller | T2 with itself | T3, T2, T1 |
['T3', 'T1', 'T2'] ['T3', 'T2', 'T1']
# test_sorts.py
# Tests for sorts.py. Run this file: it prints one line when all pass.
from sample import Sample
from sorts import insertion_sort, selection_sort, sort_by_grams
def test_numbers():
for sort in [selection_sort, insertion_sort]:
nums = [42, 18, 65, 7, 30]
sort(nums)
assert nums == [7, 18, 30, 42, 65]
empty = []
sort(empty)
assert empty == []
def test_samples():
found = [Sample("S01", "basalt", 42), Sample("S04", "mica", 7)]
sort_by_grams(found)
assert found[0].label == "S04"
test_numbers()
test_samples()
print("All sort tests passed") All sort tests passed
You sorted objects, read a stable run, and tested the edges. Tomorrow is the Mission Quest with real cards.