Python sorted() key function weirdness

Question

While I was debugging some illogical behavour I came to the following weirdness in Python 2.5 sorted() function calls:

>>> aa = [10, 5, 20]
>>> sorted(range(len(aa)))
[0, 1, 2]
sorted(range(len(aa)), key=lambda a: aa[a])
[1, 0, 2]
sorted(range(len(aa)), key=lambda a: -aa[a])
[2, 0, 1]

First two calls work as expected, but the last one is imho simply wrong! It should be: [1, 2, 0].

After further experiments for trying to come to the root of the problem I came to this (does not use lambda or negation operation, but it is otherwise the same problem):

>>> bb = [-10, -5, -20]
>>> sorted([0, 1, 2], key=bb.__getitem__)
[2, 0, 1]

Even things like following don't work and show that double negation works again:

>>> bb = [-10, -5, -20]
>>> def fun(i):
...    return bb[i]
>>> sorted([0, 1, 2], key=fun)
[2, 0, 1]
>>> def fun2(i):
...     return -bb[i]
>>> sorted([0, 1, 2], key=fun2)
[1, 0, 2]

Am I losing my mind or where is the problem? Or why doesn't Python 3.x have the cmp argument that used to work fine (compatibility is the reason why I am not using it)?

Why is the third result wrong? The values you're sorting are [0, 1, 2], and the keys are [-10, -5, -20]. Sorted that would result in [-20, -10, -5], which gives [2, 0, 1] for the values... — adw
– adw, Commented Nov 6, 2010 at 23:10
Oops, you are all right! I don't have a clue why I tought this should return something like: >>>bb = [-1, -1, -1] >>>j = 0 >>>for i in sorted(range(len(aa)), key=lambda a: -aa[a]): ... bb[i] = j ... j += 1 >>> bb [1, 2, 0] — gw0
– gw0, Commented Nov 6, 2010 at 23:32

unutbu · Accepted Answer · 2010-11-06 23:14:48Z

8

The value returned by the key function acts as a proxy for the values being sorted. So when you say

sorted(range(len(aa)), key=lambda a: -aa[a])

you are sorting range(len(aa)), that is [0, 1, 2], but using the values -aa[0], -aa[1], -aa[2] as the proxy values.

range(len(aa))   0   1   2    <-- values
aa[a]           10   5  20
-aa[a]         -10  -5 -20    <-- proxy values

Since -20, or -aa[2], is the smallest proxy value, its associated value 2 becomes the first element in the sorted result.

Since -10, or -aa[0] is the next smallest, its associated value 0 becomes the second element in the sorted result.

Finally -5, or -aa[1] is the last value, so 1 is the last number in the sorted result.

Thus, sorted(range(len(aa)), key=lambda a: -aa[a]) equals [2, 0, 1].

The answer Python is giving is correct.

answered Nov 6, 2010 at 23:14

unutbu

886k197 gold badges1.9k silver badges1.7k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Richard Fearn · Accepted Answer · 2010-11-06 23:12:19Z

the last one is imho simply wrong! It should be: [1, 2, 0]

In your second example, the key is lambda a: aa[a] which gives you the indices of the elements in increasing size order.

In the last example, the key is lambda a: -aa[a]. Due to the negation, this gives you the indices of the elements in decreasing size order.

So the last result should be [2, 0, 1] - it's the reverse of [1, 0, 2].

In this example

>>> bb = [-10, -5, -20]
>>> sorted([0, 1, 2], key=bb.__getitem__)
[2, 0, 1]

you're getting the indices of the elements in increasing size order - [2, 0, 1] corresponds to [-20, -10, -5].

In your last two examples, you're again getting the indices for the elements in increasing size order ([2, 0, 1]), or decreasing size order ([1, 0, 2]).

John La Rooy · Accepted Answer · 2010-11-06 23:11:48Z

0

This makes sense to me

>>> bb = [-10, -5, -20]
>>> sorted([0, 1, 2], key=bb.__getitem__)
[2, 0, 1]  ==> corresponds to bb.__getitem__ of [-20, -10, -5]

answered Nov 6, 2010 at 23:11

John La Rooy

306k54 gold badges378 silver badges514 bronze badges

2 Comments

user2672265 Over a year ago

i've never seen python print ==> corresponds to bb.__getitem__ of [-20, -10, -5]

Debanjan Basu Over a year ago

Neither have I seen people who seem to speak two languages :) (Apologies for having fun on SO! Resuming grumpy face! )

Collectives™ on Stack Overflow

Python sorted() key function weirdness

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related