On Sat, 2005-01-08 at 00:26, It's me wrote: > What does it mean by "stability in sorting"?
If I understand correctly, it means that when two sorts are performed in sequence, the keys that are equal to the second sort end up ordered the way they were left by the first sort. I'm far from certain of this, but at least I'm presenting an opportunity for someone to yell "no, you're wrong!" and in the process definitively answer the question. For example, given the list: .>>> l = [(1,2), (8,2), (2,2), (3,2), (4,3), (5,3), (8,9)] if we sort by the first element of each tuple then the second (the default), we get: .>>> l.sort() .>>> l [(1, 2), (2, 2), (3, 2), (4, 3), (5, 3), (8, 2), (8, 9)] Now, if we sort based on the second element we get: .>>> def seconditem(x): .... return x[1] .... .>>> l.sort(key=seconditem) .>>> l [(1, 2), (2, 2), (3, 2), (8, 2), (4, 3), (5, 3), (8, 9)] You'll note that there are several correct answers to the request "sort the list 'l' by the second element of each item", including: [(1, 2), (2, 2), (3, 2), (8, 2), (4, 3), (5, 3), (8, 9)] [(2, 2), (1, 2), (8, 2), (3, 2), (4, 3), (5, 3), (8, 9)] [(1, 2), (2, 2), (3, 2), (8, 2), (5, 3), (4, 3), (8, 9)] and many others. Because we didn't specify that the first item in the value tuples should be used in the sort key, so long as the second key is equal for a group of items it doesn't matter what order items in that group appear in. Python (at least 2.4), however, returns those groups where the order isn't defined in the same order they were before the sort. Look at this, for example: .>>> l.sort() .>>> l.reverse() .>>> l [(8, 9), (8, 2), (5, 3), (4, 3), (3, 2), (2, 2), (1, 2)] .>>> l.sort(key=seconditem) .>>> l [(8, 2), (3, 2), (2, 2), (1, 2), (5, 3), (4, 3), (8, 9)] See how the exact same sort command was used this time around, but because the list was reverse-sorted first, the elements are in reverse order by first item when the second item is equal? In the first case we used the same result as the stable sort could be obtained with: .>>> def revitem(x): .... return (x[1], x[0]) >>> l.sort(key=revitem) >>> l [(1, 2), (2, 2), (3, 2), (8, 2), (4, 3), (5, 3), (8, 9)] (in other words, saying "use the value tuple as the sort key, but sort by the second element before the first") That doesn't extend to more complex cases very well though. Imagine you had 3-tuples not 2-tuples, and wanted to maintain the previous sort order of equal groupings when re-sorting by a different key... but you didn't know what key was last used for sorting. A stable sort algorithm means you don't need to care, because the order will be maintained for you not randomized. Well, that's several hundred more words than were probably required, but I hope I made sense. -- Craig Ringer -- http://mail.python.org/mailman/listinfo/python-list
