How to sort a list of tuples according to another list

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?

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

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]

Method 2

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

Method 3

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:

• defaultdict

Method 4

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)]

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0