Lessons · Python · what sorting costs
What sorting costs, and what it buys
sorted() costs about n log n and is stable: items that compare equal keep the order they already had. That stability is a feature you can build on.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Sorting is often the cheap step that makes the real work easy. Paying n log n once to turn a comparison of every pair into a single pass is one of the best trades in programming.
How to think about it
Before writing two nested loops, ask what the order would give you. If sorted order makes 'the next one I care about' the very next item, sort first and then walk once.
Worked example
scores = [('cy', 90), ('ada', 90), ('bo', 70)]cy is before ada, and they tie.print(sorted(scores, key=lambda r: r[1]))[('bo', 70), ('cy', 90), ('ada', 90)]
print(sorted(scores, key=lambda r: -r[1]))[('cy', 90), ('ada', 90), ('bo', 70)]
readings = [41, 7, 40, 15, 8]Find the two closest values.
readings.sort()In place. sorted() would hand back a new list instead.
print(readings)[7, 8, 15, 40, 41]
closest = min(readings[i] - readings[i - 1] for i in range(1, len(readings)))One pass, not every pair.
print(closest)1
Your turn
Order the rows by score, highest first.
rows.sort(key=lambda r: r['score'], =True)
Solve one with the tests running
The trap
sort() sorts in place and returns None; sorted() returns a new list. rows = rows.sort() is the classic way to lose your data.