Sorting and Ranking

Sort Two Keys

Sort items by a primary key (category) and break ties with a secondary key (value). The trace shows remain shrinking as each minimum (cat, val) pair is selected, with result_cats and result_vals growing in tandem.

By hand

Reuse the selection-of-minimum pattern from sort-by-key, but the key function now returns a pair (cats[i], vals[i]). Python compares tuples lexicographically: category first, then value for ties. All 'a' items are therefore picked before any 'b' item, and within each category the lower value wins.

naive.py
Replay: real traced execution (multi-file project)
cats = ['b', 'a', 'b', 'a', 'b', 'a']
vals = [3, 2, 1, 3, 2, 1]
remain = list(range(len(cats)))
result_cats = []
result_vals = []
while remain:
    best = min(remain, key=lambda i: (cats[i], vals[i]))
    result_cats.append(cats[best])
    result_vals.append(vals[best])
    remain.remove(best)
print('RESULT:', list(zip(result_cats, result_vals)))

  1. cats ← ['b', 'a', 'b', 'a', 'b', 'a']

    1cats = ['b', 'a', 'b', 'a', 'b', 'a']2vals = [3, 2, 1, 3, 2, 1]
    values this step['b', 'a', 'b', 'a', 'b', 'a']cats

  2. vals ← [3, 2, 1, 3, 2, 1]

    1cats = ['b', 'a', 'b', 'a', 'b', 'a']2vals = [3, 2, 1, 3, 2, 1]3remain = list(range(len(cats)))
    values this step[3, 2, 1, 3, 2, 1]vals

  3. remain ← [0, 1, 2, 3, 4, 5]

    2vals = [3, 2, 1, 3, 2, 1]3remain = list(range(len(cats)))4result_cats = []
    values this step[0, 1, 2, 3, 4, 5]remain

  4. result_cats ← []

    3remain = list(range(len(cats)))4result_cats = []5result_vals = []
    values this step[]result_cats

  5. result_vals ← []

    4result_cats = []5result_vals = []6while remain:
    values this step[]result_vals

  6. best ← 5, result_cats ← ['a'], result_vals ← [1], remain ← [0, 1, 2, 3, 4]

    pass 1 of 6
    5result_vals = []6while remain:7    best = min(remain, key=lambda i: (cats[i], vals[i]))8    result_cats.append(cats[best])9    result_vals.append(vals[best])10    remain.remove(best)11print('RESULT:', list(zip(result_cats, result_vals)))
    values this step5best[] → ['a']result_cats[] → [1]result_vals[0, 1, 2, 3, 4, 5] → [0, 1, 2, 3, 4]remain
    All 6 passes — pass 1 is the card above
    passbestresult_catsresult_valsremain
    15[] → ['a'][] → [1][0, 1, 2, 3, 4, 5] → [0, 1, 2, 3, 4]
    25 → 1['a'] → ['a', 'a'][1] → [1, 2][0, 1, 2, 3, 4] → [0, 2, 3, 4]
    31 → 3['a', 'a'] → ['a', 'a', 'a'][1, 2] → [1, 2, 3][0, 2, 3, 4] → [0, 2, 4]
    43 → 2['a', 'a', 'a'] → ['a', 'a', 'a', 'b'][1, 2, 3] → [1, 2, 3, 1][0, 2, 4] → [0, 4]
    52 → 4['a', 'a', 'a', 'b'] → ['a', 'a', 'a', 'b', 'b'][1, 2, 3, 1] → [1, 2, 3, 1, 2][0, 4] → [0]
    64 → 0['a', 'a', 'a', 'b', 'b'] → ['a', 'a', 'a', 'b', 'b', 'b'][1, 2, 3, 1, 2] → [1, 2, 3, 1, 2, 3][0] → []

  7. while remain:

    5result_vals = []6while remain:7    best = min(remain, key=lambda i: (cats[i], vals[i]))

  8. stdout ← RESULT: [('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]

    10    remain.remove(best)11print('RESULT:', list(zip(result_cats, result_vals)))
    values this stepRESULT: [('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]stdout

The Pythonic way

zip(cats, vals) forms (cat, val) pairs; sorted(..., key=lambda pair: (pair[0], pair[1])) orders them by the same two-element tuple key. Because Python already compares tuples lexicographically, the key here is explicit but could be omitted.

library.py 
cats = ['b', 'a', 'b', 'a', 'b', 'a']
vals = [3, 2, 1, 3, 2, 1]
result = sorted(zip(cats, vals), key=lambda pair: (pair[0], pair[1]))
print('RESULT:', result)

RESULT: [('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]

Implementation notes

  • Two categories × three values keeps the data small enough that all reprs stay well within the 80-character limit.
  • The key lambda lambda i: (cats[i], vals[i]) constructs a fresh tuple for every comparison; min discards it after choosing the winner, so only the integer best appears as a traced variable.
  • result_cats and result_vals are parallel output lists that mirror the input structure; list(zip(...)) reassembles them into (cat, val) pairs for the RESULT line.