[Tutor] Sorting Nested Lists

[Steven D'Aprano]

Sarma Tangirala wrote:
> Hi list,
> 
> I was banging my head about a pythonic way of doing the following,
> 
> Given a nested list, how do I sort the uppermost list based on one key and
> when a special condition occurs a sort on another key should be performed?
> For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my example
> as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second value and
> in case they are equal, reverse sort on the first value.

That is not exactly a good example. There are at least two other ways to get 
the result you show, both much more obvious:

py> L = [[1,2], [2, 2], [3, 2], [4, 0]]
py> list(reversed(L))
[[4, 0], [3, 2], [2, 2], [1, 2]]
py> sorted(L, reverse=True)
[[4, 0], [3, 2], [2, 2], [1, 2]]


If I ignore your example, and just use the description:

"sort on the second value, and in case they are equal, reverse sort on the 
first value"

the way to do this is with a double sort. Note that this works because 
Python's sort is stable: in the event of ties, the first item remains first. 
In earlier versions of Python, this was not always the case.

So, given this list:

L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]

first sort in reverse by the first item, then by the second:


py> L.sort(key=lambda sublist: sublist[0], reverse=True)
py> L.sort(key=lambda sublist: sublist[1])
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]



Note that using a key function is MUCH more efficient than a cmp function. 
Comparison functions end up doing much more work, and hence are very much 
slower, than a key function.

Also note that in recent versions of Python, you can do without the lambda 
function and use the special "itemgetter" function:


py> from operator import itemgetter
py> L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]
py> L.sort(key=itemgetter(0), reverse=True)
py> L.sort(key=itemgetter(1))
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]


Last but not least, I will show how to do it using a custom cmp function. But 
I recommend that you don't use this!

def my_cmp(list1, list2):
     x = cmp(list1[1], list2[1])
     if x == 0:  # a tie
         x = cmp(list2[0], list1[0])  # swap the order for reverse sort
         # or if you prefer, x = -cmp(list1[0], list2[0])
     return x

sorted(L, my_cmp)




-- 
Steven