Comparing and Sorting Tuples
The DSU pattern transforms custom sorting into three simple, clear phases: decorate (add sort keys), sort (use Python's tuple comparison), and undecorate (extract results).
When Natural Order Is Not Enough
Python's built-in sorting works naturally for tasks such as ordering numbers from smallest to largest or strings alphabetically. Many useful sorting tasks require a different criterion: words might need to be ordered by length, or people might need to be ordered by age and then by name. The Decorate-Sort-Undecorate pattern, usually called DSU, turns these custom sorting tasks into three clear phases.
DSU works by placing the value used for sorting at the front of a tuple, sorting those tuples, and then extracting the original items.
The Three DSU Phases
In the Decorate phase, each original item is paired with one or more values that express the desired sorting criteria. These values appear before the original item in a tuple. In the Sort phase, Python's built-in sort method orders the decorated tuples. In the Undecorate phase, the temporary keys are removed by extracting the original items from the sorted tuples.
Ordering words by length
Arrange the words what, soft, and tree from longest to shortest, using the word itself to break ties.
Decorate: Represent each word as a tuple whose first element is its length and whose second element is the original word: (4, what), (4, soft), and (4, tree).
Sort: Sort the tuples with descending order. The first element gives the length criterion. Because all three lengths are equal, Python compares the words themselves as the next tuple element.
Undecorate: Read the second element from each sorted tuple to recover the words in their new order.
The temporary length values control the ordering, while the original words remain attached to their corresponding keys.
Reading Tuple Comparisons
The Sort phase depends on Python's tuple comparison rule. Python compares tuples element by element from left to right. It first compares the first elements. If those values are equal, it moves to the second elements. If those are also equal, it continues to the next position. This makes the first tuple element the primary criterion and later elements tie-breakers.
A tie between equal-length words
Compare the decorated tuples (4, what) and (4, soft) while sorting in descending order.
Compare the first elements: Both first elements are 4, so the length criterion does not decide the order.
Move to the second elements: Python compares what with soft. The first word begins with w and the second begins with s.
Apply descending order: With reverse=True, the larger comparison result appears first. Therefore what comes before soft.
The tuple comparison uses length first and the word itself as the tie-breaker.
Building Multiple Sort Keys
A decorated tuple can contain more than one sort key before the original item. For a list of people, the first value could represent age and the next value could represent name. Python compares age first. Only people with equal ages are compared by name. This gives DSU a direct way to express primary, secondary, and later sorting criteria.
Imagine a list of people that must be ordered by age, then by name when ages match. A decorated representation places age first, name second, and the original person record after those keys. The sort phase compares ages before names, and the undecorate phase returns the person records without the temporary keys.
Mistakes with Decorated Data
Putting the original item before the sort key
Python compares tuple elements from left to right, so the original word becomes the primary criterion instead of the desired length.
Fix:
Place the primary sort key first, followed by tie-breakers and then the original item.Ignoring tie-breaking
Equal first elements cause Python to compare the next tuple elements. The resulting order may therefore be determined by the original words or another later value.
Fix:
Choose and document the later tuple elements that should decide ties.Forgetting the undecorate phase
The DSU result has not yet been converted back to the original items.
Fix:
Extract the original element from each sorted tuple after sorting.Assuming reverse=True affects only the first key
The source describes reverse=True as reversing the sort order for all tuple elements.
Fix:
Choose tuple keys and sort direction with the effect on every element in mind.
Why DSU Is Effective
DSU is both readable and efficient because it expresses the sorting logic as data. The sort key is placed in the tuple, and Python's built-in sorting machinery performs the comparisons. This avoids the repeated function-call overhead associated with the older custom comparison-function approach and uses Python's optimized tuple comparison.
The main design decision is to choose comparable tuple values that represent the order you want. The first value should answer the primary sorting question. Later values should answer progressively narrower tie-breaking questions. The original item belongs in the decorated tuple so that it remains connected to every key throughout sorting.
Design the decorated tuple structure for a sequence of people that should be sorted by age first and name second. Identify which value belongs in position one, which belongs in position two, and where the original person record belongs.
Hints
- The first tuple element is the primary comparison criterion.
- The second tuple element is used only when ages are equal.
- Keep the original record in the tuple so it can be extracted after sorting.
The DSU Mental Checklist
- Decorate each item with a tuple whose first elements are the desired sort keys.
- Sort the decorated tuples using Python's built-in tuple ordering.
- Remember that tuple comparison proceeds from left to right and uses later elements to break ties.
- Undecorate the sorted tuples by extracting the original items.
- Check whether reverse=True should apply descending order to every tuple element.
Key Takeaways
- DSU has three phases: decorate, sort, and undecorate.
- The first tuple element is the primary sort key, while later elements provide tie-breakers.
- Python compares tuples from left to right and moves to the next element when values are equal.
- The original item stays attached to its keys during sorting and is extracted after the sorted order is established.
- reverse=True reverses the order of all tuple elements.