Sorting and tuples¶

~20 min · prerequisite: Lists and 2D grids

What you will be able to do¶

Sort with list.sort or sorted, and explain why list.sort returns None.
Control the order with a key function and reverse=True, and combine several rules in one tuple key.
Use tuples as records, and rely on the fact that Python sorts are stable.

The idea¶

Sorting puts values in order. The method a.sort() rearranges the list a itself and returns None. The function sorted(a) leaves a alone and returns a new sorted list. Think of a deck of cards: a.sort() reshuffles the deck on the table, while sorted(a) copies the deck and sorts the copy. Choose sorted when you still need the original order.

Both tools accept a key argument. Python calls the key function once for each item, then orders the items by the returned keys. For example, sorted(words, key=len) orders words by length without changing the words. The argument reverse=True flips the order. Sorting takes time that grows a little faster than the number of items, so sort once, outside your loops.

A tuple is an ordered group of values, such as (3, 5). Tuples compare item by item from the left. Python compares the first items, and looks at the second items only when the first are equal. So the key (-score, penalty, name) means: highest score first, then lowest penalty, then alphabetical name. A negative number reverses its order, which is why -score puts high scores first.

Python sorts are stable: items with equal keys keep their original order. Stability lets you sort by a secondary rule first and the main rule second. When one key is text, you cannot negate it, so this two-pass method is the usual answer.

Tuples are also immutable, so you cannot change one after you create it. That makes them safe as set members and dictionary keys.

Worked example¶

scores = [("Ada", 90, 12), ("Ben", 85, 9), ("Cy", 90, 10)]
ranked = sorted(scores, key=lambda row: (-row[1], row[2]))
print([name for name, _, _ in ranked])

The output is:

['Cy', 'Ada', 'Ben']

Line by line, this is what Python does:

Each row is a tuple of a name, a score, and a penalty.
sorted makes a new list and leaves scores unchanged.
The key for Ada is (-90, 12), and for Cy it is (-90, 10). The scores tie, so the smaller penalty wins, and Cy comes first.
Ben has the key (-85, 9). Because -85 is larger than -90, Ben comes last.

Try it¶

The first block shows that sort returns None. The second block shows that equal keys keep their order. The third block sorts text in two passes.

def demo():
    a = [3, 1, 2]
    result = a.sort()
    assert result is None
    assert a == [1, 2, 3]

    b = [3, 1, 2]
    c = sorted(b)
    assert b == [3, 1, 2]
    assert c == [1, 2, 3]

demo()

items = [("a", 1), ("b", 0), ("c", 1), ("d", 0)]
by_value_desc = sorted(items, key=lambda p: p[1], reverse=True)
assert [name for name, _ in by_value_desc] == ["a", "c", "b", "d"]

words = ["bb", "a", "cc", "b"]
ordered = sorted(sorted(words), key=len, reverse=True)
assert ordered == ["bb", "cc", "a", "b"]

Common mistakes¶

Using the result of sort. Writing result = nums.sort() and then result[0] gives:
```
TypeError: 'NoneType' object is not subscriptable
```
Call nums.sort() on its own, or write result = sorted(nums).
Mixing types. Running sorted(["b", 2]) gives:
```
TypeError: '<' not supported between instances of 'int' and 'str'
```
Convert the values to one type before you sort.
Negating text. Writing sorted(words, key=lambda w: -w) gives:
```
TypeError: bad operand type for unary -: 'str'
```
Use reverse=True, or the two-pass method.
Reversing too much. With rows = [(90, "Ada"), (90, "Ben")], the call sorted(rows, reverse=True) also reverses the names. To reverse only the score, use sorted(rows, key=lambda r: (-r[0], r[1])).

Unpacking the wrong count. Writing a, b = (1, 2, 3) gives:

ValueError: too many values to unpack (expected 2, got 3)

Practice¶

Write the function named in each problem. The samples are checks you can run by hand.

Descending numbers (easy). Write descending(values). Return the integers from largest to smallest. Sample: descending([5, -2, 9, 0]) returns [9, 5, 0, -2].
Words by length (easy). Write by_length(words). Sort by length, then alphabetically. Sample: by_length(["pear", "fig", "apple", "kiwi"]) returns ["fig", "kiwi", "pear", "apple"].
Leaderboard (medium). Write standings(rows). Each row is (name, score, penalty). Higher score comes first, then lower penalty, then alphabetical name. Return the names. Sample: standings([("Alice", 300, 45), ("Bob", 350, 60), ("Charlie", 300, 30), ("Dana", 300, 30)]) returns ["Bob", "Charlie", "Dana", "Alice"].
Stable by value (medium). Write ids_by_value(pairs). Each pair is (id, value). Sort by value, keeping input order for equal values. Return the ids. Sample: ids_by_value([(1, 5), (2, 3), (3, 5), (4, 3)]) returns [2, 4, 1, 3].
Closest point (stretch). Write closest(points). Each point is (x, y). Choose the point with the smallest x*x + y*y, breaking ties by smaller x, then smaller y. Sample: closest([(3, 4), (1, 1), (0, 5), (-1, 1)]) returns (-1, 1).

Solution

```python def descending(values): return sorted(values, reverse=True)

assert descending([5, -2, 9, 0]) == [9, 5, 0, -2] ```

```python def by_length(words): return sorted(words, key=lambda w: (len(w), w))

assert by_length(["pear", "fig", "apple", "kiwi"]) == ["fig", "kiwi", "pear", "apple"] ```

```python def standings(rows): ranked = sorted(rows, key=lambda r: (-r[1], r[2], r[0])) return [name for name, _, _ in ranked]

rows = [("Alice", 300, 45), ("Bob", 350, 60), ("Charlie", 300, 30), ("Dana", 300, 30)] assert standings(rows) == ["Bob", "Charlie", "Dana", "Alice"] ```

```python def ids_by_value(pairs): return [i for i, _ in sorted(pairs, key=lambda p: p[1])]

assert ids_by_value([(1, 5), (2, 3), (3, 5), (4, 3)]) == [2, 4, 1, 3] ```

```python def closest(points): return min(points, key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))

assert closest([(3, 4), (1, 1), (0, 5), (-1, 1)]) == (-1, 1) ```

Recap¶

a.sort() changes the list and returns None. sorted(a) returns a new list.
A tuple key compares its parts from left to right, and -x reverses a number.
Python sorts are stable, so you can sort by a secondary rule first and by the main rule second.