Start learning free

LESSON 563 OF 569 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Sort Your Own Objects in Python: Defining __lt__

Practice O(n log n) Read the full explanation

A language can sort numbers and strings on its own: it already knows which of two of them comes first. For objects of your own class it doesn't, until the class tells it. Every language has a way for a class to say how two of its objects compare. Once a class has it, the language's own sort can sort a list of those objects, with no comparison written at the call.

Write:

  • a class Student, created by Student(name, grade), that can compare itself with another student: a student comes first if their grade is higher; when two grades are equal, the name that comes first in alphabetical order (A to Z) comes first;
  • a method rank_students(students) in the class Solution, which sorts the students with your language's own sort, using that comparison, and returns their names in that order.

In Python, a class becomes comparable by defining __lt__(self, other): it returns True when self comes before other. a < b calls it, and so do the list's sort() and sorted().

Don't write your own sorting loop. The program also checks your comparison directly: for each two neighbours in the list you return, it asks Student whether the first one comes before the second.

 

Example 1:

Input: students = [("Ana", 90), ("Bob", 85), ("Cid", 90)]
Output: Ana Cid Bob
Explanation: Ana and Cid have the highest grade, 90. They tie, so their names decide: Ana comes before Cid.
Bob, with 85, comes last.

Example 2:

Input: students = [("Eve", 55), ("Dan", 100), ("Bea", 0), ("Cal", 99)]
Output: Dan Cal Eve Bea
Explanation: All the grades are different, so only the grades decide, from 100 down to 0.

Example 3:

Input: students = [("Max", 88), ("Leo", 88), ("Anna", 88), ("Ann", 88)]
Output: Ann Anna Leo Max
Explanation: Everyone has the same grade, so the list is in alphabetical order.
"Ann" comes before "Anna": when one name is the start of the other, the shorter one comes first.

 

Constraints:

  • There are 1 to 100 students.
  • 0 <= grade <= 100
  • A name has 2 to 10 letters: a capital letter, then lowercase letters. No two students have the same name.
Note:

The language's sort takes O(n log n) comparisons for n students, and each comparison takes constant time.

STEP 1 OF 8
    Ctrl + Enter to check

    PYTHON · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Sort Your Own Objects in Python, explained

    Problem overview

    Python can sort numbers and strings because it knows which of two of them comes first. For objects of your own class it does not, until the class says how two of them compare. The lesson asks for:

    • a class Student, created with Student(name, grade), where a student comes first if the grade is higher, and when the grades are equal the name that comes first alphabetically comes first;
    • a method rank_students(students) in the class Solution that sorts the students with the list's own sort and returns their names in that order.

    For Ana (90), Bob (85) and Cid (90), the result is Ana Cid Bob. Ana and Cid tie on 90, so their names decide, and Bob has the lowest grade.

    Approach: teach the class to compare, then let sort do the work

    Writing your own sorting loop is not needed. Python's list.sort() only asks one question about two items: does the first one come before the second? It asks it with the < operator. When a < b is written for two objects of your class, Python calls a.__lt__(b). If Student defines __lt__, sorting a list of students just works, with no key argument.

    The method returns True when self comes before other. Here that means two rules, checked in order:

    1. If the grades differ, the student with the higher grade comes first, so return self.grade > other.grade. The comparison is reversed on purpose: "first" means "highest grade".
    2. If the grades are equal, compare the names with <. Python compares strings letter by letter, so "Ana" < "Cid" is True, and when one name is the start of another the shorter one is smaller: "Ann" < "Anna" is True.

    Step by step

    1. Store the data. In __init__, set self.name and self.grade. They stay public because rank_students reads each name.
    2. Handle different grades. In __lt__, if self.grade != other.grade, return self.grade > other.grade.
    3. Handle equal grades. Return self.name < other.name.
    4. Sort in place. In rank_students, call students.sort() with no arguments.
    5. Collect the names. Start an empty list names, loop over the sorted students and append student.name.
    6. Return names.

    The solution in Python

    class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade

    def __lt__(self, other):
        if self.grade != other.grade:
            return self.grade > other.grade
        return self.name < other.name

class Solution:
    def rank_students(self, students):
        students.sort()
        names = []
        for student in students:
            names.append(student.name)
        return names

    Using it on the examples:

    solution = Solution()
data = [("Ana", 90), ("Bob", 85), ("Cid", 90)]
print(*solution.rank_students([Student(n, g) for n, g in data]))

data = [("Eve", 55), ("Dan", 100), ("Bea", 0), ("Cal", 99)]
print(*solution.rank_students([Student(n, g) for n, g in data]))

data = [("Max", 88), ("Leo", 88), ("Anna", 88), ("Ann", 88)]
print(*solution.rank_students([Student(n, g) for n, g in data]))

    Ana Cid Bob
Dan Cal Eve Bea
Ann Anna Leo Max

    The comparison can also be used directly:

    a = Student("Ana", 90)
b = Student("Bob", 85)
print(a < b, b < a)

    True False

    Ana comes before Bob because 90 is higher than 85, so a < b is True even though 90 is not less than 85. In this class, "less than" means "ranks earlier".

    Why only __lt__

    sort() and sorted() use only <, so __lt__ is the one method needed for sorting. Without it, sorting a list of your objects fails:

    TypeError: '<' not supported between instances of 'NoLt' and 'NoLt'

    That message comes from a class named NoLt that has no __lt__. Operators such as >, <= or == are separate methods (__gt__, __le__, __eq__). They are not needed here, and the tests check only the order of the names.

    Edge cases and common mistakes

    • Reversed grade comparison. Writing self.grade < other.grade puts the lowest grade first. The lesson wants the highest first.
    • Reversing the name comparison too. Names go A to Z, so use < for the name and > only for the grade.
    • Prefix names. "Ann" comes before "Anna": the shorter name is smaller when it is the start of the other.
    • Lowercase and uppercase. Python compares letters by code, so any uppercase letter is smaller than any lowercase one. The lesson's names are a capital letter followed by lowercase letters, so this does not come up.
    • Returning the students instead of the names. The method returns a list of name strings.
    • Sorting a copy. students.sort() changes the list and returns None. If you want to keep the original order, use sorted(students), which returns a new list.

    Complexity

    Python's sort makes O(n log n) comparisons for n students, and each comparison takes constant time, so sorting is O(n log n). Collecting the names is another O(n).

    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free