How to check if a list of dictionaries is sorted?

Question

I have created a list of dictionaries:

l = []
d = {"a":1,"b",2}
l.append(d)
d = {"a":5,"b":6}
l.append(d)
d = {"a":3,"b":4}
l.append(d)

Now, how do I check whether the list of dictionaries is sorted or not based on the key a or key b?

Can you explain what makes a list of dictionaries “sorted” by your definition? I don't think this is a well-defined property. — 5gon12eder, Nov 27 '15 at 03:52

score 3 · Answer 1 · answered Nov 27 '15 at 03:55

3

print(l == sorted(l, key=lambda d:d["a"]))
False

answered Nov 27 '15 at 03:55

Dyno Fu

8,753
4
39
64

This is O(n log n) _at best_, while my answer is O(1) at best, and O(n) at worst. – orlp Nov 27 '15 at 04:48
yes. this just an intuitive solution. when performance matters, one can always try something more optimized like yours. – Dyno Fu Nov 27 '15 at 05:00

score 2 · Accepted Answer · answered Nov 27 '15 at 03:52

2

Just use the default check if something is sorted, but index before comparing:

k = "a"
all(l[i][k] <= l[i+1][k] for i in range(len(l) - 1))

answered Nov 27 '15 at 03:52

orlp

112,504
36
218
315

score 1 · Answer 3 · edited May 23 '17 at 11:44

As discussed in this answer, you can efficiently check if a list is sorted using:

all(l[i] <= l[i+1] for i in xrange(len(l)-1))

To support a custom key, you can define something like

def is_sorted(iterable, key=None):
    if key is None:
        key = lambda x : x
    return all(key(iterable[i]) <= key(iterable[i+1]) for i in xrange(len(iterable)-1))

In this case, you can just use a simple lambda function looking up the dictionary values as the key (assuming all elements are dicts containing a and b), e.g.

# Check if list of dictionaries are sorted by value of 'a'
>>> is_sorted(l, key=lambda x: x["a"])

# Check if list of dictionaries are sorted by value of 'b'
>>> is_sorted(l, key=lambda x: x["b"])

# Check if list of dictionaries are sorted by value of 'a', then 'b'
>>> is_sorted(l, key=lambda x: (x["a"], x["b"]))

How to check if a list of dictionaries is sorted?

3 Answers3