Sorting Lists of Tuples
Python compares tuples element-by-element from left to right, stopping at the first index where elements differ.
The First Difference
When Python compares two tuples, it does not treat each tuple as one indivisible object. It examines corresponding elements from left to right: first index 0, then index 1, then index 2, and so on. As soon as it finds a pair of unequal elements, that pair determines the comparison result. Python stops there and ignores every later element.
The comparison is decided by the first unequal pair, not by the largest value anywhere in either tuple.
A Comparison Trace
Finding the stopping index
Compare the tuples (0, 1, 2000000) and (0, 3, 4).
Index 0: The values are 0 and 0. They are equal, so Python continues to the next position.
Index 1: The values are 1 and 3. They differ, and 1 is less than 3. This determines that the first tuple is less than the second.
Index 2: Python does not use 2000000 and 4 to decide the result because the comparison already stopped at index 1.
(0, 1, 2000000) is less than (0, 3, 4).
Equal Prefixes
Tuple length matters only after every shared position has been found equal. If one tuple contains all the elements of the other in the same order and then ends, the shorter tuple is less than the longer tuple. The shorter tuple is called a prefix of the longer tuple in this situation.
Comparing different lengths
Compare the tuples (2, 5) and (2, 5, 0).
Shared index 0: Both tuples contain 2, so the comparison continues.
Shared index 1: Both tuples contain 5, so all shared elements are equal.
End of the shorter tuple: The first tuple ends while the second tuple still has an element.
(2, 5) is less than (2, 5, 0).
Do not compare a missing element with the next element of the longer tuple. If all shared elements are equal, the tuple that ends first is less.
Later Values Ignored
A common mistake is to scan every value and decide based on a later value that looks more important or much larger. Python does not calculate an overall size for the tuple. It uses the first position where the tuples differ. Therefore, two tuples can contain very different later elements while still having a comparison result determined by an earlier position.
Comparing the largest elements first
Python reaches the unequal values 1 and 3 at index 1 before it would consider index 2.
Fix:
Compare from index 0 toward the right and stop at the first unequal pair.Continuing after finding an unequal pair
The comparison has already been decided by 1 and 3.
Fix:
Record the result at the first difference and ignore later positions.Assuming equal shared elements make different-length tuples equal
One tuple is a prefix of the other, so the shorter tuple is less than the longer tuple.
Fix:
After matching all shared positions, check which tuple ends first.
Sorting Several Tuples
Python uses this same element-by-element comparison when sorting a list of tuples. It first orders tuples by their first elements. If two tuples have equal first elements, their second elements determine their relative order. The process continues to later positions only when earlier positions match.
Ordering a list of tuples
Determine the sorted order of [(3, 1), (3, 0), (2, 5)].
Place the tuple beginning with 2: (2, 5) comes before both tuples beginning with 3 because 2 is less than 3.
Compare the remaining tuples: (3, 1) and (3, 0) have equal first elements, so Python compares their second elements.
Use the second elements: 0 is less than 1, so (3, 0) comes before (3, 1).
[(2, 5), (3, 0), (3, 1)]
Prediction Practice
What do you think happens?
Which tuple is less: (4, 2, 900) or (4, 7, 1)?
Reveal answer
Answer: (4, 2, 900)
The values at index 0 are equal. At index 1, 2 is less than 7, so Python stops there and does not use 900 or 1.
Predict the sorted order of [(1, 9), (1, 2), (0, 8)]. State which index determines each important placement.
Hints
- Compare the first elements before considering the second elements.
- For the two tuples beginning with 1, compare their second elements.
Summary
- Python compares tuple elements from left to right.
- The first unequal pair determines the result, and later elements are ignored.
- If all shared elements are equal, the shorter tuple is less than the longer tuple.
- Large later values cannot overturn a result decided at an earlier index.
- Sorting a list of tuples uses the same comparison process.
Key Takeaways
- Tuple comparison proceeds from the first position toward the last.
- The comparison stops immediately at the first unequal pair.
- A tuple that is an equal prefix of a longer tuple is less than that longer tuple.
- Later values, even very large ones, do not matter after an earlier difference.
- Python sorts lists of tuples by applying this same lexicographic comparison rule.