[Tutor] sorting nested tuples [decorate-sort-undecorate]

[Danny Yoo]

On Fri, 17 Oct 2003, Conrad Koziol wrote:

> if I have a list
>
>
> x = [('hello', 2), ('goodbye', 3), ('python', 1)]
>
> how would i sort it by the 2 variable or any variable for that matter.


Hi Conrad,


A quick way to do it is to "decorate" the list:

###
>>> mylist = [('hello', 2), ('goodbye', 3), ('python', 1)]
>>> for i, e in enumerate(mylist):
...     mylist[i] = (e[1], e)
...
>>> mylist
[(2, ('hello', 2)), (3, ('goodbye', 3)), (1, ('python', 1))]
###


And this is something that can now be sorted!

###
>>> mylist.sort()
>>> mylist
[(1, ('python', 1)), (2, ('hello', 2)), (3, ('goodbye', 3))]
###


So it's sorted, but it's still decorated.  So we need to "undecorate"
the list:

###
>>> for i, e in enumerate(mylist):
...     mylist[i] = e[1]
...
>>> mylist
[('python', 1), ('hello', 2), ('goodbye', 3)]
###

This is the "decorate-sort-undecorate" pattern.  We take advantage of
Python's native sort() method, and augment/deaugment our structure just
enough to make things work nicely.

The Perl folks have popularized this technique as the "Schwartzian
Transform".  If you do a search on that term, you'll can find more
examples of this technique.  The technique is especially nice on Python
because tuples are directly comparable --- and tuples can contain tuples!
--- so we don't have anything really ugly to do the decoration.

If you'd like to know more, Andrew Dalke Sorting mini-HOWTO tutorial is a
good resource:

    http://www.amk.ca/python/howto/sorting/sorting.html


Good luck to you!