sorting on keys in a list of dicts

Nick Coghlan ncoghlan at iinet.net.au
Fri Jan 7 18:17:23 CET 2005


It's me wrote:
> What does it mean by "stability in sorting"?
> 
> Can somebody please give a sample for using the code posted?  I am a little
> lost here and I like to know more about the use of keys....

It's the jargon for what Jeff said - if you are sorting by some value calculated 
from each list entry, and different list entries may give the same value, then a 
stable sort guarantees that the order of entries giving the same value will be 
preserved from the original list.

Consider:

Py> from operator import itemgetter as item
Py> seq = [(1, 1), (2, 1), (2, 3), (1, 5)]
Py> seq.sort(key=item(1))
Py> seq #1
[(1, 1), (2, 1), (2, 3), (1, 5)]
Py> seq.sort(reverse=True)
Py> seq #2
[(2, 3), (2, 1), (1, 5), (1, 1)]
Py> seq.sort(key=item(1))
Py> seq #3
[(2, 1), (1, 1), (2, 3), (1, 5)]

This snippet sorts the tuples according to the second item, then sorts them in 
reverse order of the whole tuple, then resorts them according to the second item.

Notice that the order of the first two items is different between point #1 and 
point #3. This is because sorting by the second item makes no distinction 
between these two tuples, and they retain whatever order they had before the 
sort began.

This is what it means to have a stable sort, and it makes expressing complex 
sorting quite easy by chaining different sort operations together.

Python 2.3 has a stable sort, and Python 2.4 brought the guarantee that it shall 
remain that way. I'm not sure about Python 2.2 and earlier.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net



More information about the Python-list mailing list