Sort a list of tuples with two tuple entries in opposite order

Question

Hopefully this will make sense...

I have a list of tuples of the following form:

list_of_tuples = [('a', 1), ('b', 3), ('b', 2), ('a', 3)]

The desired output is

sorted_list_of_tuples = [('a', 1), ('b', 2), ('b', 3), ('a', 3)]

The issue is I want the second entry to be increasing, and the first entry to be decreasing.

import operator as op     
sorted_list_of_tuples = sorted(list_of_tuples, key=op.itemgetter(2, 0))

This, of course, sorts both fields to be increasing. I can't come up with a cute (i.e., couple of lines) way to do this. Does anyone have a way to accomplish this kind of sorting easily?

I seem to remember that you can reference elements of a list comprehension inside the brackets using _, so maybe that's a place to start?

Maybe I wasn't clear: the integer in this case is more important. It's order should be increasing across the list. When there's a tie (ie.., the second entry is equal), I want 'b' to occur before 'a'.

*I seem to remember that you can reference elements of a list comprehension inside the brackets using _, so maybe that's a place to start?* - I'm not sure what you are referring to, but `_` is nothing special in Python, just a variable name. — Gareth Latty, May 02 '13 at 22:26
@Lattyware: I understand. What I recalled reading was in this thread: http://stackoverflow.com/questions/101268/hidden-features-of-python See the entry titled "Referencing a list comprehension as it is being built..." — BenDundee, May 02 '13 at 22:40
As noted there, that's an obscure implementation detail, and not something to be used in general. It's also not really relevant here. — Gareth Latty, May 02 '13 at 22:42
@BenDundee: That's an undocumented implementation artifact of older versions of CPython. I'm pretty sure it doesn't even work in 2.7 or 3.x. EDIT: Verified that it does not work in CPython 2.7, 3.2, or 3.3, or PyPy 1.9 or 2.0. It does work in CPython 2.5 and 2.6. — abarnert, May 02 '13 at 22:43
@abarnert In sincerely doubt it would in 3.x, as list comps are now just syntactic sugar for `list()` wrapping a generator expression. — Gareth Latty, May 02 '13 at 22:44
@Lattyware: Sure, but as I said, it's _also_ broken in 2.7 (and PyPy), where list comps are still semantically unchanged. — abarnert, May 02 '13 at 22:48
@abarnert Oh, I imagined so, I was just backing up the statement. — Gareth Latty, May 02 '13 at 22:55

abarnert · Accepted Answer · 2013-05-02T22:34:15.183

If you can describe the key in English, just translate that to a function.

I want the second entry to be increasing, and the first entry to be decreasing.

So, the key is:

def make_key(my_tuple):
    return my_tuple[1], -my_tuple[0]

Except, of course, that - doesn't work that way on strings, so you need something fancier.

Or, maybe not… while the first element of each tuple is a string, the second is an integer, so, we can just negate the key function, and use reverse to un-negate it:

def make_key(my_tuple):
    return -my_tuple[1], my_tuple[0]

sorted_list_of_tuples = sorted(list_of_tuples, key=make_key, reverse=True)

If you want to save a few keystrokes:

sorted_list_of_tuples = sorted(list_of_tuples,
                               key=lambda x: (x[1], x[0]), reverse=True)

This isn't the only trick that would work here. For example, because all of your strings are 1-character strings, ord(x) < ord(y) iff x < y.

But sometimes you can't think of an easy trick—but you can think of an easy way to write a comparison function. If it's more readable, do it that way:

def compare_my_tuples(lhs, rhs):        
    if rhs[1] > lhs[0]: return 1
    elif rhs[1] < lhs[0]: return -1
    elif rhs[0] > lhs[0]: return -1
    elif rhs[0] < rhs[0]: return 1
    else: return 0

sorted_list_of_tuples = sorted(list_of_tuples, 
                               key=functools.cmp_to_key(compare_my_tuples))

Or, of course, you can split it into two sorts, as in steveha's answer. (Yes, it might take twice as long… but in most apps, that won't make any difference at all.)

steveha · Answer 2 · 2013-05-02T22:31:31.833

2

Sure. Python's built-in sort is a "stable" sort. So, pick which sort you want to be more important, and do that one second. Do the less-important sort, then sort again by the more-important criteria.

Working code:

import operator as op

list_of_tuples = [('a', 1), ('b', 3), ('b', 2), ('a', 3)]

list_of_tuples.sort(key=op.itemgetter(0), reverse=True)
list_of_tuples.sort(key=op.itemgetter(1))

assert list_of_tuples == [('a', 1), ('b', 2), ('b', 3), ('a', 3)]

I guess you can do the whole thing in one pass if you come up with a clever key function. Maybe this:

def custom_key_fn(tup):
    ch, n = tup # unpack tuple
    return (n, -ord(ch))

list_of_tuples = [('a', 1), ('b', 3), ('b', 2), ('a', 3)]
list_of_tuples.sort(key=custom_key_fn)

assert list_of_tuples == [('a', 1), ('b', 2), ('b', 3), ('a', 3)]

edited May 02 '13 at 22:31

answered May 02 '13 at 22:26

steveha

74,789
21
92
117

You can't do it with a single sort? – BenDundee May 02 '13 at 22:29
@BenDundee: Sure you can, it just takes a more complex key function. It's a tradeoff. – abarnert May 02 '13 at 22:34
+1 Using a 2-pass sort is much cleaner and easier to understand, it should scale pretty well with Timsort anyway. Avoid the temptation to be clever unless it's performance critical code. – wim May 03 '13 at 01:40

Sort a list of tuples with two tuple entries in opposite order

2 Answers2