Sort List Of Tuples With Multiple Criteria

I have a list of tuples of k elements. I'd like to sort with respect to element 0, then element 1 and so on and so forth. I googled but I still can't quite figure out how to do it.

Solution 1:

Since python's sort is stable for versions after 2.2 (or perhaps 2.3), the easiest implementation I can think of is a serial repetition of sort using a series of index, reverse_value tuples:

# Specify the index, and whether reverse should be True/False
sort_spec = ((0, True), (1, False), (2, False), (3, True))

# Sort repeatedly from last tuple to the first, to have final output be# sorted by first tuple, and ties sorted by second tuple etcfor index, reverse_value in sort_spec[::-1]:
    list_of_tuples.sort(key = lambda x: x[index], reverse=reverse_value)

This does multiple passes so it may be inefficient in terms of constant time cost, but still O(nlogn) in terms of asymptotic complexity.

If the sort order for indices is truly 0, 1... n-1, n for a list of n-sized tuples as shown in your example, then all you need is a sequence of True and False to denote whether you want reverse or not, and you can use enumerate to add the index.

sort_spec = (True, False, False, True)
for index, reverse_value inlist(enumerate(sort_spec))[::-1]:
    list_of_tuples.sort(key = lambda x: x[index], reverse=reverse_value)

While the original code allowed for the flexibility of sorting by any order of indices.

Incidentally, this "sequence of sorts" method is recommended in the Python Sorting HOWTO with minor modifications.

Edit If you didn't have the requirement to sort ascending by some indices and descending by others, then

fromoperator import itemgetter
list_of_tuples.sort(key = itemgetter(1, 3, 5))

will sort by index 1, then ties will be sorted by index 3, and further ties by index 5. However, changing the ascending/descending order of each index is non-trivial in one-pass.

Solution 2:

list.sort(key = lambda x : (x[0], x[1], ...., x[k-1])

This is actually using the tuple as its own sort key. In other words, the same thing as calling sort() with no argument.

If I assume that you simplified the question, and the actual elements are actually not in the same order you want to sort by (for instance, the last value has the most precedence), you can use the same technique, but reorder the parts of the key based on precedence:

list.sort(key = lambda x : (x[k-1], x[1], ...., x[0])

In general, this is a very handy trick, even in other languages like C++ (if you're using libraries): when you want to sort a list of objects by several members with varying precedence, you can construct a sort key by making a tuple containing all the relevant members, in the order of precedence.

Final trick (this one is off topic, but it may help you at some point): When using a library that doesn't support the idea of "sort by" keys, you can usually get the same effect by building a list that contains the sort-key. So, instead of sorting a list of Obj, you would construct then sort a list of tuples: (ObjSortKey, Obj). Also, just inserting the objects into a sorted set will work, if they sort key is unique. (The sort key would be the index, in that case.)

Solution 3:

So I am assuming you want to sort tuple_0 ascending, then tuple_1 descending, and so on. A bit verbose but this is what you might be looking for:

ctr = 0for i inrange(list_of_tuples):
    if ctr%2 == 0:
        list_of_tuples[0] = sorted(list_of_tuples[0])
    else:
        list_of_tuples[0] = sorted(list_of_tuples[0], reverse=True)
    ctr+=1print list_of_tuples