Entry

How should a sortable sequence be implemented?

Keyed Tree as sorted sequence: Slice & Key access?

Aug 21st, 2000 21:56
unknown unknown, Charles Hixson, Will Ware

Objects can be sorted as long as they can be compared. Fundamental
types (ints, floats, strings) can be compared with the globally defined
cmp() function. cmp(x,y) returns a negative integer if x<y, zero if 
x==y, and a positive integer if x>y. If the 'sort' method is called on a 
list of objects, the list will be sorted in increasing order:
x = [3,1,4,1,5,9,2,6]
x.sort()
print x  -->  [1,1,2,3,4,5,6,9]
Classes can be made sortable by defining a __cmp__ method for them. For
example, to sort a list of 3-d points in decreasing order of z, you 
could write:
class Point:
    def __init__(self, x,y,z):
        self.x, self.y, self.z = x, y, z
    def __cmp__(self, other):
        return -cmp(self.z, other.z)
        # or: return cmp(other.z, self.z)
Now if you create a list of points (x) and call x.sort(), the points 
will be sorted in decreasing-z order.
Another way to define the sorting criterion is to pass a cmp-like 
function as the argument to x.sort(). To re-sort your points in 
increasing-y order, you can write:
x.sort(lambda self,other: cmp(self.y, other.y))
or if you don't like lambdas:
def y_sorter(u,v):
    return cmp(u.y, v.y)
x.sort(y_sorter)