is this sort method the same as the one in python 2.4
Raymond Hettinger
vze4rx4y at verizon.net
Sun Jan 30 18:08:42 EST 2005
"Lowell Kirsh"
> How come you reverse the list twice? And why does this preserve stability?
It's easy to see if you trace through the steps:
Given sample the following dataset and a desire to sort on the first field:
>>> data = [('a', 1), ('a', 2), ('b', 3)]
Here are the step:
>>> data.reverse()
>>> data
[('b', 3), ('a', 2), ('a', 1)]
>>> data.sort(key=lambda record: record[0])
>>> data
[('a', 2), ('a', 1), ('b', 3)]
>>> data.reverse()
>>> data
[('b', 3), ('a', 1), ('a', 2)]
Note, in the final result, the two equal records (the ones with 'a') appear in
the same order as the original dataset (that is what stability means).
Now, try it without the initial reversal and note that stability is not
preserved:
>>> data = [('a', 1), ('a', 2), ('b', 3)]
>>> data.sort(key=lambda record: record[0])
>>> data.reverse()
>>> data
[('b', 3), ('a', 2), ('a', 1)]
Here's another way of accomplishing the original sort and preserving stability:
>>> data = [('a', 1), ('a', 2), ('b', 3)]
>>> sorted(data, cmp = lambda x,y: cmp(y[0], x[0]))
[('b', 3), ('a', 1), ('a', 2)]
Raymond Hettinger
More information about the Python-list
mailing list