Sorting a dictionary by its value, and then its key if values are equal then outputting a list

Question

map={"a":5, "b":2, "c":7, "d":5, "e":5}

output should be:

['c', 'a', 'd', 'e', 'b']

So, the code should first assort the dictionary in descending order by its value, and then if its value is the same it should sort by the key in ascending order. So far I have...

newmap=map
newmap=sorted(newmap.iteritems(), key=operator.itemgetter(1,0),reverse=True)
print newmap

This gives me the output [('c', 7), ('e', 5), ('d', 5), ('a', 5), ('b', 2)]. So, I need to get the e, d, a in ascending order... without messing up the sorts of the numbers. How do I do this?

Answer 1

In my answer, I replaced map with dct to not mask the built-in function.

Sorted keys by inverse value, then by key in ascending order:

sorted(dct, key=lambda k: (-dct[k], k))

By turning the value into a negative number, this sorts on value in reverse, while keys are sorted in ascending order.

Demo:

>>> dct = {'a': 5, 'c': 7, 'b': 2, 'e': 5, 'd': 5}
>>> sorted(dct, key=lambda k: (-dct[k], k))
['c', 'a', 'd', 'e', 'b']

Timing comparisons:

>>> import timeit
>>> timeit.timeit("sorted(dct, key=lambda k: (-dct[k], k))", 'from __main__ import dct')
4.741436004638672
>>> timeit.timeit("map(operator.itemgetter(0), sorted(dct.items(), key=lambda i: (-i[1], i[0])))", 'from __main__ import dct; import operator')
7.489126920700073
>>> timeit.timeit("map(operator.itemgetter(0), sorted(sorted(dct.iteritems()), key=operator.itemgetter(1), reverse=True))", 'from __main__ import dct; import operator')
10.01669192314148

Answer 2

Sorting is guaranteed to be stable in Python, so all you have to do is sort twice: first on the key, then on the value.

sorted_pairs = sorted(sorted(map.iteritems()), key=operator.itemgetter(1), reverse=True)

To get just the keys from this output you can use a list comprehension:

[k for k,v in sorted_pairs]

P.S. don't name your variables the same as Python types or you're going to be very surprised some day.