Comparing and Sorting Tuples
DSU works by placing the value used for sorting at the front of a tuple, sorting those tuples, and then extracting the original items.
Try it: Sorting with key= and reverse=
How sorted() and list.sort() compute key(item) once per item, order the items by those keys with Python's comparison rules, and keep equal keys in their original order — including py4e's sort-a-dict-by-value pattern.
How it works
- Decorate: call the key function once on every item (no key means the item itself is compared).
- Compare keys with Python's rules: ints by value, strs by code point ('Z' < 'a'), tuples item by item.
- Order the items by key; reverse=True puts the largest key first.
- Stable: items with equal keys keep their original relative order, also with reverse=True.
- sorted() returns a new list; list.sort() rearranges the list in place and returns None; [:N] keeps the first N.
Default run (12 steps): 5 items in their original order. Python will call lambda t: t[1] once per item. … sorted() returned a new list: result = [('fig', 5), ('kiwi', 5), ('pear', 3), ('apple', 3), ('date', 1)].
Simplified: Up to 10 items of one kind (ints, short ASCII words, (word, count) tuples or a small dict) and a fixed menu of key functions. The sorting algorithm itself (Timsort) is not shown — only what it guarantees: the order by key and stability.
Loading the simulation…
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.
- 1Decorate
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).
- 2Sort
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.
- 3Undecorate
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.
- 1Compare the first elements
Both first elements are 4, so the length criterion does not decide the order.
- 2Move to the second elements
Python compares what with soft. The first word begins with w and the second begins with s.
- 3Apply 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
Common mistake Putting the original item before the sort key
What it looks likeA tuple is organized with the word first and its length later.
Why it failsPython compares tuple elements from left to right, so the original word becomes the primary criterion instead of the desired length.
Do this insteadPlace the primary sort key first, followed by tie-breakers and then the original item.
Common mistake Ignoring tie-breaking
What it looks likeSeveral words have the same length, but no later tuple element is considered.
Why it failsEqual 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.
Do this insteadChoose and document the later tuple elements that should decide ties.
Common mistake Forgetting the undecorate phase
What it looks likeThe final result is left as a sequence of tuples containing temporary keys.
Why it failsThe DSU result has not yet been converted back to the original items.
Do this insteadExtract the original element from each sorted tuple after sorting.
Common mistake Assuming reverse=True affects only the first key
What it looks likeA tuple has a primary key and a secondary key, but descending order is expected for only one of them.
Why it failsThe source describes reverse=True as reversing the sort order for all tuple elements.
Do this insteadChoose 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
- 1Decorate each item with a tuple whose first elements are the desired sort keys.
- 2Sort the decorated tuples using Python's built-in tuple ordering.
- 3Remember that tuple comparison proceeds from left to right and uses later elements to break ties.
- 4Undecorate the sorted tuples by extracting the original items.
- 5Check 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.