[Tutor] Re: Sorting Instance Attributes

[Danny Yoo]

On Thu, 12 Dec 2002, Alan Colburn wrote:

> Let's start with the cmp function/method. I understand that the function
> returns -1 if the first item is less than the second, 0 if they're
> equal, and 1 if the first item is greater than the second.

Yes.



> The part I don't know about relates to using the function/method with a
> list of items; I only understand using it to compare two items.

I'm interpreting this question as: "Once I have this comparison function,
what good is it when I'm sorting a list of items?"  Stop me if I'm
completely missing your question.  *grin*


Python's sort() method uses the comparison function repeatedly between
pairs of elements in a list.  If a pair of elements are misordered --- in
descending order --- then Python swaps those two elements so that they're
now ascending.  We can almost imagine that the disorder of the list
gradually drops to zero as Python does repeated swaps and comparisons on
the list.



It's hard to believe that doing repeated swaps actually accomplishes
anything, so it's pretty neat that this actually works.  But we don't need
to just believe it in theory: we can actually see this comparison in
action!  Let's hijack the comparison function so that it prints out the
state of a list of numbers as a list gradually gets sorted.

###
>>> numbers = [random.randrange(100) for i in range(10)]
>>> numbers
[55, 82, 79, 74, 57, 58, 74, 58, 78, 62]
>>> def mycmp(a, b):
...     global numbers
...     print "my numbers list is", numbers
...     print "I'm comparing", a, "and", b
...     return cmp(a, b)
...
>>> numbers.sort(mycmp)
my numbers list is [55, 82, 79, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 82 and 55
my numbers list is [55, 82, 79, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 79 and 82
my numbers list is [55, 82, 79, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 79 and 82
my numbers list is [55, 82, 79, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 79 and 55
my numbers list is [55, 79, 82, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 74 and 79
my numbers list is [55, 79, 82, 74, 57, 58, 74, 58, 78, 62]
I'm comparing 74 and 55
my numbers list is [55, 74, 79, 82, 57, 58, 74, 58, 78, 62]
I'm comparing 57 and 79
my numbers list is [55, 74, 79, 82, 57, 58, 74, 58, 78, 62]
I'm comparing 57 and 74
my numbers list is [55, 74, 79, 82, 57, 58, 74, 58, 78, 62]
I'm comparing 57 and 55
my numbers list is [55, 57, 74, 79, 82, 58, 74, 58, 78, 62]
I'm comparing 58 and 74
my numbers list is [55, 57, 74, 79, 82, 58, 74, 58, 78, 62]
I'm comparing 58 and 57
my numbers list is [55, 57, 58, 74, 79, 82, 74, 58, 78, 62]
I'm comparing 74 and 74
my numbers list is [55, 57, 58, 74, 79, 82, 74, 58, 78, 62]
I'm comparing 74 and 82
my numbers list is [55, 57, 58, 74, 79, 82, 74, 58, 78, 62]
I'm comparing 74 and 79
my numbers list is [55, 57, 58, 74, 74, 79, 82, 58, 78, 62]
I'm comparing 58 and 74
my numbers list is [55, 57, 58, 74, 74, 79, 82, 58, 78, 62]
I'm comparing 58 and 57
my numbers list is [55, 57, 58, 74, 74, 79, 82, 58, 78, 62]
I'm comparing 58 and 58
my numbers list is [55, 57, 58, 58, 74, 74, 79, 82, 78, 62]
I'm comparing 78 and 74
my numbers list is [55, 57, 58, 58, 74, 74, 79, 82, 78, 62]
I'm comparing 78 and 79
my numbers list is [55, 57, 58, 58, 74, 74, 79, 82, 78, 62]
I'm comparing 78 and 74
my numbers list is [55, 57, 58, 58, 74, 74, 78, 79, 82, 62]
I'm comparing 62 and 74
my numbers list is [55, 57, 58, 58, 74, 74, 78, 79, 82, 62]
I'm comparing 62 and 58
my numbers list is [55, 57, 58, 58, 74, 74, 78, 79, 82, 62]
I'm comparing 62 and 58
>>> numbers
[55, 57, 58, 58, 62, 74, 74, 78, 79, 82]
###


The action is very gradual on this list, but we do see that the list
gradually becomes more and more sorted until the sort() stops.  All the
while, Python's doing cmp()'s on pairs of elements, and making some
decisions based on the comparisons.


I hope this helps!