sorting list of tuples by second (third...) tuple item

[Jeff Shannon]

Marcus Stojek wrote:

> Hi,
>
> I am still struggling with tuple-lists.
>
> How can I sort a list of tuples (all tuples have 4 float items)
> by the second (or third or n-th) tuple item. And I have to
> do it fast.

You can supply a custom comparison function to sort(), such as
this:

def mycmp(first, second):
    return cmp( first[2], second[2] )

mylist.sort(mycmp)

But this tends to be pretty slow.  For large lists, it's usually
considered that the "decorate-sort-undecorate" pattern is the most
effective way.  Something like this:

def SortOnItem(mylist, index):
    templist = [ (line[index], line) for line in mylist ]
    templist.sort()
    return [ line[1:] for line in templist ]

What this does is build a separate list containing a tuple of the
element that you want to sort on, and the entire line, sorts that
list (by the first element, of course), and then strips that first
element off.  This can use a lot of memory (you're creating two
copies of your original list, but they are only references, not
deep copies), but until you hit memory constraints this is likely
to be faster than a custom cmp() function.  (The custom cmp() makes
an extra function call for *each* line of the list, and function
calls are relatively expensive in Python.)

(Of course, the list comprehensions require Python 2.x; if you're
stuck on 1.5.2, the equivalent can be done with map/filter/lambda.)

Jeff Shannon
Technician/Programmer
Credit International