python - How to sort a list of tuples according to another list

45
votes

There is a list:

a = [("ax", 1), ("ec", 3), ("bk", 5)]

another list: 

b = ["ec", "ax", "bk"]

I want to sort a according to b:

sort_it(a, b)

a = [("ec", 3), ("ax", 1), ("bk", 5)]

How to do this?

4
pythonlistsorting
@jpp this is in fact not a duplicate of stackoverflow.com/q/6618515/519015. This question is about aligning the ordering of one list with that of another, whereas the other question is about using the values of the second list as the sort key for the first. Try the solution given there and you will see that it does not produce the desired result. Likewise if you try to apply the accepted solution here to the case there you will get a ValueError. - Aryeh Leib Taurog
@AryehLeibTaurog, I appreciate the sentiment, so I have opened it up again. In my mind, they are both adaptations of each other. If one solution is understood, the other is obvious. What we don't want to go down is the road we have a separate solution for len-2 tuples, len-3 tuples, len-4 tuples, etc. - jpp

4 Answers

66
votes
a.sort(key=lambda x: b.index(x[0]))

This sorts a in-place using the the index in b of the first element of each tuple from a as the values it sorts on.

Another, possibly cleaner, way of writing it would be:

a.sort(key=lambda (x,y): b.index(x))

If you had large numbers of items, it might be more efficient to do things a bit differently, because .index() can be an expensive operation on a long list, and you don't actually need to do a full sorting since you already know the order:

mapping = dict(a)
a[:] = [(x,mapping[x]) for x in b]

Note that this will only work for a list of 2-tuples. If you want it to work for arbitrary-length tuples, you'd need to modify it slightly:

mapping = dict((x[0], x[1:]) for x in a)
a[:] = [(x,) + mapping[x] for x in b]
2
votes

Another posibility is to sort a, sort the indices of b according to b and than sort the a according to the indices

a.sort(key=lambda x: x[0])
ind = [i[0] for i in sorted(enumerate(b),key=lambda x: x[1])]
a = [i[0] for i in sorted(zip(a,ind),key=lambda x: x[1])]

since every sorting takes n*log(n) this is still scalable for bigger lists

2
votes

There's actually a way to do this in linear O(n) time, because this isn't really a sorting operation. The existence of the list b means that the sorting is already done; all we really need to do is to rearrange the elements of a to be in the same order. This can be done efficiently thanks to dictionaries.

from collections import defaultdict

def sorted_by(seq_to_sort, desired_order, key=None):
    if key is None:
        key = lambda x: x

    # group the elements by their key
    grouped_items = defaultdict(list)
    for item in seq_to_sort:
        k = key(item)
        grouped_items[k].append(item)

    # flatten the dict of groups to a list
    return [item for key in desired_order for item in grouped_items[key]]

Usage:

a = [("ax", 1), ("ec", 3), ("bk", 5)]
b = ["ec", "ax", "bk"]
result = sorted_by(a, b, lambda tup: tup[0])
print(result)  # output: [("ec", 3), ("ax", 1), ("bk", 5)]

Notes:

  • This is a stable sort; if two list items have the same key, their order will be preserved. Example:

    >>> sorted_by([1, 2, 3], [5], key=lambda x: 5)
[1, 2, 3]

  • If any list elements are mapped to keys that don't exist in desired_order, those elements are silently discarded. For example:

    >>> sorted_by([1, 2, 3], [1, 2, 3], key=lambda x: 5)
[]

See also:

0
votes

Traditional sorting may not be needed.

[tup for lbl in b for tup in a if tup[0] == lbl]
# [('ec', 3), ('ax', 1), ('bk', 5)]