Fail in sorting a list of objects in Python using compare and lt

Question

I can't make this code work. I've tried what I've seen browsing the net. Most indications suggest to use __cmp__ but it doesn't work. Also, I've tried using __lt__ with the same unsuccessful results.

Can anyone keep an eye on my code and tell me how to get it to work correctly?

I've created a Vertex class (Vertice) with it's initializer, __lt__, __gt__ and __cmp__ methods. Also, a main program that creates a list of Vertex and tries to order them (unsuccessfully).

---

class Vertice:
    def __init__(self, coordenada_x, coordenada_y):
        self.coordenada_x = coordenada_x
        self.coordenada_y = coordenada_y

    def __str__(self):
        return "Vértice ({},{})".format(self.coordenada_x, self.coordenada_y)

    def __add__(self, otro_vertice):
        vertice_resultado = Vertice(self.coordenada_x + otro_vertice.coordenada_x, self.coordenada_y + otro_vertice.coordenada_y)
        return vertice_resultado


    def __lt__(self, otro_vertice):
        if self.coordenada_x > otro_vertice.coordenada_x:
            return -1
        elif self.coordenada_x < otro_vertice.coordenada_x:
            return +1
        else:
            if self.coordenada_y > otro_vertice.coordenada_y:
                return -1
            elif self.coordenada_y < otro_vertice.coordenada_y:
                return +1
            else:
                return 0

    def __gt__(self, otro_vertice):
        if self.coordenada_x > otro_vertice.coordenada_x:
            return +1
        elif self.coordenada_x < otro_vertice.coordenada_x:
            return -1
        else:
            if self.coordenada_y > otro_vertice.coordenada_y:
                return +1
            elif self.coordenada_y < otro_vertice.coordenada_y:
                return -1
            else:
                return 0

    def __cmp__(self, otro_vertice):
        if self.coordenada_x > otro_vertice.coordenada_x:
            return +1
        elif self.coordenada_x < otro_vertice.coordenada_x:
            return -1
        else:
            if self.coordenada_y > otro_vertice.coordenada_y:
                return +1
            elif self.coordenada_y < otro_vertice.coordenada_y:
                return -1
            else:
                return 0

---

from Vertice import Vertice
import random

def main():
    lista = []
    for i in range(0,10):
        a = random.randint(1,99)
        b = random.randint(1,99)
        lista.append(Vertice(a,b))

    for elemento in lista:
        print(elemento)

    print()

    lista.sort()

    for elemento in lista:
        print(elemento)

    print()

main()

I expect the output of a list of Vertex firstly ordered by it's "x" coordinate and secondly by it's "y" coordinate. At this moment the list is reordered chaotically.

Answer 1

First, as noted in Odds and Ends documentation on sorting:

The sort routines are guaranteed to use __lt__() when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method

It's also mentioned in the sort() documentation:

This method sorts the list in place, using only < comparisons between items.

So you only need to implement an __lt__ method.
You don't need __gt__ and __cmp__ is not anymore valid for Python3.

Next, the __lt__ method must return either True or False.

# is self < other_vertice?
def __lt__(self, other_vertice):        
    if self.x > other_vertice.x:
        return False
    elif self.x < other_vertice.x:
        return True
    else:
        if self.y > other_vertice.y:
            return False
        elif self.y < other_vertice.y:
            return True
        else:
            return False

After that, your code in main should now work:

def main():
    lista = []
    for i in range(0, 10):
        a = random.randint(1, 2)
        b = random.randint(1, 99)
        lista.append(Vertice(a, b))
    print("UNSORTED")
    for elemento in lista:
        print(elemento)

    print("SORTED")
    lista.sort()
    for elemento in lista:
        print(elemento)

main()

Result:

UNSORTED
Vértice (48,44)
Vértice (5,92)
Vértice (46,10)
Vértice (55,51)
Vértice (63,54)
Vértice (53,85)
Vértice (95,18)
Vértice (69,84)
Vértice (8,20)
Vértice (97,64)
SORTED
Vértice (5,92)
Vértice (8,20)
Vértice (46,10)
Vértice (48,44)
Vértice (53,85)
Vértice (55,51)
Vértice (63,54)
Vértice (69,84)
Vértice (95,18)
Vértice (97,64)

Result (when some vertices have the same x):

UNSORTED
Vértice (1,88)
Vértice (1,65)
Vértice (2,87)
Vértice (2,4)
Vértice (2,69)
Vértice (2,81)
Vértice (2,5)
Vértice (1,36)
Vértice (1,97)
Vértice (1,73)
SORTED
Vértice (1,36)
Vértice (1,65)
Vértice (1,73)
Vértice (1,88)
Vértice (1,97)
Vértice (2,4)
Vértice (2,5)
Vértice (2,69)
Vértice (2,81)
Vértice (2,87)