Start learning free

LESSON 567 OF 573 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Sort Your Own Objects in TypeScript: compareTo and sort

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 rankStudents(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.

TypeScript's sort has no comparison interface to look for. The convention is a method compareTo(other) that returns a negative number when this student comes first, a positive number when other does, and 0 when they are equal; sort gets a function that calls it.

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 9
    Ctrl + Enter to check

    TYPESCRIPT · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Sort Your Own Objects in TypeScript, explained

    Problem overview

    JavaScript can sort numbers and strings because it knows how to order them. For objects of your own class it doesn't, until you say how two of them compare. You write a class Student, created by Student(name, grade), with a method compareTo(other), and a method rankStudents(students) in Solution that sorts the students with the array's own sort and returns their names in that order.

    The ranking rule: a higher grade comes first. When two grades are equal, the name that comes first alphabetically comes first. For Ana (90), Bob (85) and Cid (90), the answer is Ana Cid Bob: Ana and Cid tie at 90, and Ana's name comes before Cid's.

    Approach: put the rule in the class

    TypeScript has no interface that sort looks for. The convention is a method compareTo(other) that returns a negative number when this student comes first, a positive number when other comes first, and 0 when they are equal. Array.prototype.sort asks for exactly that kind of answer from a comparison function: negative means the first argument goes first. So rankStudents passes a small function that hands the work to compareTo. The rule lives in the class, and no sorting loop is written.

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

    Step by step

    1. Fields. Declare name: string and grade: number in Student. They stay public because rankStudents reads each name.
    2. Constructor. Store both parameters in this.name and this.grade.
    3. Grades first. If the grades differ, return other.grade - this.grade. A higher grade must rank first, so when this has the bigger grade the result is negative.
    4. Names second. With equal grades, return this.name.localeCompare(other.name). It is negative when this.name comes first alphabetically, so students with the same grade go from A to Z.
    5. Sort. Call students.sort with a function of first and second that returns first.compareTo(second).
    6. Collect the names. Make an empty string[] with const, loop over the sorted students with for...of, push each student.name and return the array.

    The solution in TypeScript

    class Student {
    name: string;
    grade: number;

    constructor(name: string, grade: number) {
        this.name = name;
        this.grade = grade;
    }

    compareTo(other: Student): number {
        if (this.grade !== other.grade) {
            return other.grade - this.grade;
        }
        return this.name.localeCompare(other.name);
    }
}

class Solution {
    rankStudents(students: Student[]): string[] {
        students.sort((first, second) => first.compareTo(second));
        const names: string[] = [];
        for (const student of students) {
            names.push(student.name);
        }
        return names;
    }
}

    TypeScript details worth knowing:

    • sort changes the array in place. It also returns the same array. After rankStudents runs, the list you passed in is in ranked order too. To keep the original order, sort a copy: [...students].sort(...).
    • sort with no comparison is not enough. Without a function, sort turns elements into strings and compares those. For numbers that gives [10, 9, 1].sort() equal to [1, 10, 9]. For Student objects, every string is [object Object], so nothing moves.
    • The comparison function is a rule, not a boolean. It returns a number: negative, zero or positive. Returning true or false doesn't say which of three outcomes applies.
    • Subtracting works for grades. Grades are whole numbers from 0 to 100, so other.grade - this.grade is a safe, exact difference. For strings you can't subtract, which is why names use localeCompare.
    • localeCompare returns a number. It is negative, zero or positive, and "Ann".localeCompare("Anna") is negative: when one name is the start of the other, the shorter comes first.

    Seeing it run

    const s = new Solution();
const mk = (xs: [string, number][]) => xs.map(([n, g]) => new Student(n, g));
console.log(s.rankStudents(mk([["Ana", 90], ["Bob", 85], ["Cid", 90]])).join(" "));
console.log(s.rankStudents(mk([["Eve", 55], ["Dan", 100], ["Bea", 0], ["Cal", 99]])).join(" "));
console.log(s.rankStudents(mk([["Max", 88], ["Leo", 88], ["Anna", 88], ["Ann", 88]])).join(" "));
console.log(new Student("Ana", 90).compareTo(new Student("Bob", 85)));
console.log(new Student("Bob", 85).compareTo(new Student("Ana", 90)));
console.log(new Student("Ana", 90).compareTo(new Student("Ana", 90)));
    Ana Cid Bob
Dan Cal Eve Bea
Ann Anna Leo Max
-5
5
0

    In the second list all the grades differ, so only the grades decide, from 100 down to 0. In the third list everyone has 88, so the names decide, and Ann comes before Anna. The last three lines call compareTo directly: Ana against Bob is -5 because Ana's 90 beats Bob's 85, the reverse is 5, and two equal students give 0.

    The sort is only as good as compareTo. The lesson's tests also call your comparison directly on each pair of neighbours in the ranked list, so the method has to be right on its own, not just good enough to produce the right order for the examples.

    Edge cases and common mistakes

    • Reversed subtraction. this.grade - other.grade ranks the lowest grade first. The higher grade must give a negative result, so it is other.grade - this.grade.
    • Ignoring ties. Without the name rule, students with equal grades stay in whatever order they started in. Example 1 depends on Ana coming before Cid.
    • Comparing names with -. Subtracting strings gives NaN, not a useful order. Use localeCompare.
    • Calling sort() bare. It leaves the students where they are, as explained above.
    • Writing a sorting loop. The point of the lesson is that the class knows the rule and the language's sort does the sorting.
    • A single student. A list of one is already sorted; the comparison is never called and the answer is that one name.
    • Surprised caller. Because sort reorders the input array, a caller that still needs the original order should pass a copy.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free