Sort a list of dictionary with order of specific key

Question

I have a list of dict like this:

data = [{"uid": "a1", "name": "b1"}, 
        {"uid": "a3", "name": "b3"}, 
        {"uid": "a4", "name": "b4"},
        {"uid": "a5", "name": "b5"}]

Now I want to sort that list with the order of the uid field like this:

uid_order = ['a1', 'a5', 'a3', 'a4']

Which means the output should be:

[{"uid": "a1", "name": "b1"}, 
 {"uid": "a5", "name": "b5"},
 {"uid": "a3", "name": "b3"},
 {"uid": "a4", "name": "b4"}]

Of course, I can create a new empty list then use 2 for loops to check and add every element, but is there any elegant way (or better complexity) to do this?

Does this answer your question? [How do I sort a list of dictionaries by a value of the dictionary?](https://stackoverflow.com/questions/72899/how-do-i-sort-a-list-of-dictionaries-by-a-value-of-the-dictionary) — Alex Telon, Mar 28 '20 at 11:02
Nope, that answer only work if `uid_order` is already in decending/ascending order — ExplodingGayFish, Mar 28 '20 at 11:10
I see. My bad I saw what I expected to see when reading the question, should have seen the specific order you requested. Would updating the heading to "Sort a list of dictionaries on key in non-standard order" be an improvement maybe? It will be easier for other to find if they have the same question I think. — Alex Telon, Mar 28 '20 at 11:33

score 4 · Accepted Answer · answered Mar 28 '20 at 15:16

4

O(n) solution:

>>> [*map({d['uid']: d for d in data}.get, uid_order)]
[{'uid': 'a1', 'name': 'b1'},
 {'uid': 'a5', 'name': 'b5'},
 {'uid': 'a3', 'name': 'b3'},
 {'uid': 'a4', 'name': 'b4'}]

answered Mar 28 '20 at 15:16

Kelly Bundy

23,480
7
29
65

`list(...)` is arguably cleaner than `[*...]`, but this is very neat – Mad Physicist Mar 28 '20 at 16:06
@MadPhysicist I used to think so, too, but I'm getting used to `[*...]` and I like it for the consistency with `[2, 3, 5]` and `[]`. Maybe one day everyone is going to use it, except of course those people who today still write `set([...])` insted of `{...}` :-) – Kelly Bundy Mar 28 '20 at 16:08

Mad Physicist · Answer 2 · 2020-03-28T08:30:16.947

You can sort a list in place with it's sort method if you want to avoid making a new list. This will use Timsort, which has O(n log n) complexity, much better than your suggested O(n^2) implementation:

uid_order = {k: i for i, k in enumerate(uid_order)}
data.sort(key=uid_order.get)

To speed up lookup into uid_order, I invert it into a dictionary (invert because a list maps index to item, while you want item to index). Instead of an O(n) lookup at each evaluation of the key, you have an O(1) lookup now.

An alternative way to make the dictionary using only function calls:

uid_order = dict(map(reversed, enumerate(uid_order)))

See also: Python Sorting HOW TO

Sebastian Baltser · Answer 3 · 2020-03-28T08:09:02.810

2

With the sorted-function you can specify a key that the function should sort after. You want to access the value of the "uid" key for each dictionary and that value's index in uid_order determines that dictionary's index in the sorted list:

sorted(data, key = lambda x: uid_order.index(x["uid"]))

What this code means is, each element of the list gets passed to the lambda-function. The resulting value is used as key to sort after.

edited Mar 28 '20 at 08:09

answered Mar 28 '20 at 08:03

Sebastian Baltser

718
4
11

Very nice, I love the one line code but unfortunately I'm looking for better performance so I have to accept @Mad Physicist solution, sorry about that :D – ExplodingGayFish Mar 28 '20 at 11:17

Sort a list of dictionary with order of specific key

3 Answers3