Problem overview
Kotlin 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 does not, until the class says how two of its objects compare. Once it does, the standard sorted() works on a collection of them, with no comparison written where you call it.
You write two things:
- a class
Student(name, grade)that can compare itself with another student: 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
rankStudents(students)in the classSolutionthat sorts the students with Kotlin'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 grade 90, so their names decide, and Bob with 85 comes last.
Approach
Kotlin's way for a class to describe its natural order is the interface Comparable<Student>. It has one method, compareTo(other), which must return:
- a negative number when this student comes first;
- a positive number when
othercomes first; - 0 when they are equal.
Once Student implements it, sorted() uses it to order the students, and so do the operators < and >. You never write a sorting loop. The work is a good compareTo.
The comparison has two rules in a fixed order. First compare the grades, and the higher grade wins. Only if the grades are equal do you look at the names.
Step by step
- Give the class the header
class Student(val name: String, val grade: Int) : Comparable<Student>. Thevalparameters create the properties, and the interface name after the colon has no parentheses. - In
compareTo, if the grades differ, returnother.grade - grade. When this student's grade is bigger, the result is negative, which means "this one comes first". That is the reverse of the usual order, because here a higher grade ranks first. - When the grades are equal, return
name.compareTo(other.name). AStringalready compares itself alphabetically, negative when it comes first. - In
rankStudents, writeval ranked = students.sorted(). It returns a newListin order and leaves the original array as it was. - Create
val names = mutableListOf<String>(), loop overrankedand add eachstudent.name. - Return
names.
The solution in Kotlin
class Student(val name: String, val grade: Int) : Comparable<Student> {
override fun compareTo(other: Student): Int {
if (grade != other.grade) {
return other.grade - grade
}
return name.compareTo(other.name)
}
}
class Solution {
fun rankStudents(students: Array<Student>): List<String> {
val ranked = students.sorted()
val names = mutableListOf<String>()
for (student in ranked) {
names.add(student.name)
}
return names
}
}
Kotlin details:
compareToneeds theoverridekeyword, because it comes from the interface.sorted()only compiles for elements that areComparable. On a class without that interface, the compiler reports that no candidate ofsorted()applies to the receiver type.- An
Array<Student>has its ownsorted(), which returns aList, not an array. That is why the result type isList<String>.
A run
With the three examples, rankStudents returns:
[Ana, Cid, Bob]
[Dan, Cal, Eve, Bea]
[Ann, Anna, Leo, Max]The inputs are, in order, Ana 90, Bob 85, Cid 90; Eve 55, Dan 100, Bea 0, Cal 99; and Max 88, Leo 88, Anna 88, Ann 88. In the second, all grades differ, so they alone decide. In the third, everyone has the same grade, so the order is alphabetical. Ann comes before Anna: when one name is the start of the other, the shorter one comes first.
The comparison also works on its own, for example with the operators:
println(Student("Ana", 90) < Student("Bob", 85))
println(Student("Ann", 88).compareTo(Student("Anna", 88)) < 0)
println(Student("Ana", 90).compareTo(Student("Ana", 90)))
true
true
0Another way: a comparator at the call
Kotlin can also sort a class that is not Comparable, if you pass the rule at the call. For a plain class Student(val name: String, val grade: Int):
val ranked = students.sortedWith(compareBy({ -it.grade }, { it.name }))
It gives [Ana, Cid, Bob] for the first example. This lesson asks for the other design, where the class itself knows its order and the call stays a bare sorted(). Putting the rule in the class means no caller can forget it, every place that sorts students agrees on the same order.
Complexity
The sort makes O(n log n) comparisons for n students, and each comparison takes constant time, so ranking takes O(n log n) time. The sorted list and the list of names need O(n) extra space.
Edge cases and common mistakes
- Getting the direction wrong.
grade - other.gradewould put the lowest grade first. For a high-to-low order the subtraction must beother.grade - grade. - Comparing names in the wrong order. The tie-break is alphabetical from A to Z, so keep
name.compareTo(other.name)and don't swap the two. - Subtracting in general. Subtraction is safe here because grades run from 0 to 100. For arbitrary
Intvalues it can overflow:Int.MAX_VALUE - (-1)wraps to-2147483648, a negative number, although the first value is larger.Int.MAX_VALUE.compareTo(-1)returns1correctly. - Returning students instead of names. The method returns the names, so read each student's
nameproperty. - Writing your own sorting loop. The task asks for the language's own sort driven by
compareTo.
