Start learning free

LESSON 567 OF 573 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Sort Your Own Objects in Scala: Ordered

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.

In Scala, Student extends Ordered[Student]: its method compare(other) returns a negative number when this student comes first, a positive number when other does, and 0 when they are equal. sorted and < use 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 7
    Ctrl + Enter to check

    SCALA · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Sort Your Own Objects in Scala, explained

    Problem overview

    Scala can sort numbers and strings on its own, because it knows which of two of them comes first. For objects of your own class it doesn't, until the class says how two of its objects compare. After that, the standard sorted works on an array of those objects, with no comparison written at the call.

    The lesson asks for two things:

    • a class Student(name, grade) that can compare itself with another student: a higher grade comes first, and when the grades are equal, the name that comes first from A to Z comes first;
    • a method rankStudents(students) in Solution that sorts the students with Scala's own sort and returns their names in that order.

    For Ana (90), Bob (85) and Cid (90), the answer is Ana Cid Bob. Ana and Cid tie on 90, so their names decide, and Bob comes last.

    Approach

    In Scala, a class becomes sortable by extending Ordered[Student] and defining compare(other). The method returns a negative number when this student comes first, a positive number when other does and 0 when they are equal. With it, sorted can order the array, and the operators < and > work on students as well.

    The rule for compare has two parts:

    1. If the grades differ, the higher grade comes first. other.grade - grade is negative exactly when this student's grade is bigger.
    2. If the grades are equal, use the names. A string's compareTo is negative when the first string comes first alphabetically.

    Then rankStudents sorts and collects the names. No sorting loop is needed.

    Step by step

    1. In compare, when grade != other.grade, return other.grade - grade.
    2. Otherwise, return name.compareTo(other.name).
    3. In rankStudents, create ranked as students.sorted. This returns a new array and leaves the original alone.
    4. Create an empty ArrayBuffer[String] called names.
    5. Loop over ranked and add each student.name with +=.
    6. Return names.toList.

    The solution in Scala

    class Student(val name: String, val grade: Int) extends Ordered[Student] {
    override def compare(other: Student): Int = {
        if (grade != other.grade) {
            return other.grade - grade
        }
        return name.compareTo(other.name)
    }
}

class Solution {
    def rankStudents(students: Array[Student]): List[String] = {
        val ranked = students.sorted
        val names = scala.collection.mutable.ArrayBuffer[String]()
        for (student <- ranked) {
            names += student.name
        }
        return names.toList
    }
}

    Details worth knowing:

    • Why sorted works. It needs an ordering for Student. Because Student extends Ordered[Student], Scala finds one. Without the extends, Array(...).sorted doesn't compile: No implicit Ordering defined.
    • Only the sign matters. Sorting looks at whether the result is negative, zero or positive, not at its size.
    • Cost. The sort makes O(n log n) comparisons for n students, and each comparison takes constant time for names up to 10 letters.

    Trying it

    The comparison can be called directly:

    val ana = new Student("Ana", 90)
val bob = new Student("Bob", 85)
println(ana.compare(bob))
println(bob.compare(ana))
println(ana < bob)
println(ana > bob)

    This prints:

    -5
5
true
false

    Ana ranks before Bob, so ana < bob is true: for an Ordered class, "less" means "comes first". Ranking whole lists gives:

    • Eve 55, Dan 100, Bea 0, Cal 99 give Dan Cal Eve Bea. All the grades differ, so only the grades decide.
    • Max, Leo, Anna and Ann, all with grade 88, give Ann Anna Leo Max. A name that is the start of another comes first, so Ann precedes Anna.

    Why a subtraction works as a comparison

    Sorting needs to know which of two items goes first, and the answer can be any negative number, zero or any positive number. That is why subtracting works. For Ana (90) and Bob (85), other.grade - grade is 85 - 90 = -5: negative, so Ana comes first. Seen from Bob, it is 90 - 85 = 5: positive, so the other student comes first. The two answers agree, which a comparison must always do.

    The grades are small whole numbers, from 0 to 100, so the subtraction can't overflow an Int. For large values, Integer.compare would be the safer way to compare two numbers, because a difference of two big numbers can wrap around.

    The tie

    For Ana and Cid, both with 90, the grade check is skipped and the names decide. "Ana".compareTo("Cid") is negative, so Ana comes first. For "Ann" and "Anna", the shorter one is the start of the longer one and gets the negative result, so it comes first.

    Edge cases

    A single student sorts to a list of one name. Grades of 0 and 100 are valid and sort like any others. No two students share a name, so two students never compare as equal in the lesson's tests, but compare still returns 0 for the same name and grade, which is what Ordered expects. Names are a capital letter followed by lowercase letters, so the alphabetical order of compareTo is the order a person expects.

    Common mistakes

    • Reversing the grade subtraction. grade - other.grade would put the lowest grade first. The higher grade must give a negative result, which is other.grade - grade.
    • Forgetting the tie. Equal grades must fall back on the names, or the order of equal students stays arbitrary.
    • Comparing names with -. Strings can't be subtracted. Use compareTo.
    • Writing a sorting loop. The lesson wants Scala's own sorted, which uses compare.
    • Returning students instead of names. The method returns a List[String].
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free