Problem overview
Swift can sort numbers and strings because it knows which of two of them comes first. For a class of your own it doesn't, until the class says so. Write a class Student, created by Student(name, grade), that compares itself with another student: a higher grade comes first, and when grades are equal the name that is first in alphabetical order comes first. Then write rankStudents(_:) in Solution: it sorts the students with Swift'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 and Ana's name comes first.
Approach
A class that conforms to the Comparable protocol can be sorted with sorted() and no arguments. The protocol needs <, which says whether the left student comes before the right one, and ==, because Comparable also requires Equatable. Sorting takes O(n log n) comparisons for n students, each of constant time, and the loop that collects the names is O(n). No sorting loop is written.
Step by step
- Declare
let name: Stringandlet grade: Int, and store theinitparameters in them. - Write
static func <with parameterslhsandrhs. If the grades differ, returnlhs.grade > rhs.grade: the higher grade comes first. - If the grades are equal, return
lhs.name < rhs.name. Strings compare letter by letter. - Write
static func ==: both the name and the grade are equal. - In
rankStudents, callstudents.sorted(), loop over the result and append eachstudent.nameto an array that is returned.
The solution in Swift
class Student: Comparable {
let name: String
let grade: Int
init(_ name: String, _ grade: Int) {
self.name = name
self.grade = grade
}
static func < (lhs: Student, rhs: Student) -> Bool {
if lhs.grade != rhs.grade {
return lhs.grade > rhs.grade
}
return lhs.name < rhs.name
}
static func == (lhs: Student, rhs: Student) -> Bool {
return lhs.name == rhs.name && lhs.grade == rhs.grade
}
}
class Solution {
func rankStudents(_ students: [Student]) -> [String] {
let ranked = students.sorted()
var names = [String]()
for student in ranked {
names.append(student.name)
}
return names
}
}
The three examples of the lesson, with the names joined by spaces:
let s = Solution()
func r(_ x: [(String, Int)]) {{ print(s.rankStudents(x.map {{ Student($0.0, $0.1) }}).joined(separator: " ")) }}
r([("Ana",90),("Bob",85),("Cid",90)])
r([("Eve",55),("Dan",100),("Bea",0),("Cal",99)])
r([("Max",88),("Leo",88),("Anna",88),("Ann",88)])
Ana Cid Bob
Dan Cal Eve Bea
Ann Anna Leo Max
In the last list everyone has the same grade, so only names decide, and "Ann" comes before "Anna" because the shorter name goes first when one is the start of the other.
Swift details worth knowing
<is "comes before". It doesn't have to mean "smaller". Here a higher grade is "less", so the best student sorts first.static. The operator belongs to the type and gets both students as parameters.==is required. Without it, the compiler saystype 'Student' does not conform to protocol 'Equatable', with the note that automatic synthesis ofEquatableis not supported for class declarations (a struct can get it automatically).- Other operations come free. Once
<is defined,Student("Ann", 5) < Student("Anna", 5)istrue, andmax()on an array of students gives the one that sorts last.
Edge cases and common mistakes
- Comparing the grades the wrong way.
lhs.grade < rhs.gradewould put the lowest grade first. - Forgetting the tie-break. Equal grades would then come out in no meaningful order.
- Strictness.
<must be false for two equal students:Student("Ann", 5) < Student("Ann", 5)isfalse. - Writing your own loop. The point is that
sorted()uses the class's own comparison.
Tracing the first example
The students are Ana 90, Bob 85 and Cid 90. Among the comparisons the sort makes with < are these. Ana against Cid: the grades are equal, so the names decide, and "Ana" < "Cid" is true, so Ana comes before Cid. Ana against Bob: 90 is higher than 85, so lhs.grade > rhs.grade is true and Ana comes first. Cid against Bob: the same. The result is Ana, Cid, Bob, and the method returns ["Ana", "Cid", "Bob"], which the program prints as Ana Cid Bob.
Because the lesson also checks the comparison directly, on each pair of neighbours in the list you return, it must give true for the first against the second. A comparison that sorts correctly but is wrong for ties would fail that check.
What sorted() does with your comparison
When sorted() has to decide the order of two students, it asks the class's own <. You never call that function yourself. Take three students created in the order Cid 90, Ana 90, Bob 85:
let list = [Student("Cid", 90), Student("Ana", 90), Student("Bob", 85)]
print(list.sorted().map {{ $0.name }})
print(list.sorted(by: {{ $0.name < $1.name }}).map {{ $0.name }})
["Ana", "Cid", "Bob"]
["Ana", "Bob", "Cid"]
The first line uses the class's comparison: grades first, names to break the tie. The second passes a closure that compares names only, so Bob moves ahead of Cid. That is the usual way to sort by a one-off rule. Defining the comparison once in the class means every place that calls plain sorted() gets the same order, with no closure to repeat.
The == function
Two students are equal when both the name and the grade match, so Student("Ana", 90) == Student("Ana", 90) is true and Student("Ana", 90) == Student("Ana", 80) is false. The lesson says names are never repeated, so the sort doesn't depend on ==, but the protocol requires it. With the order defined, the largest student by that order is also available: list.max() gives Bob, the one that sorts last.
Key takeaways
- Define
<and==and conform toComparableto make a class sortable. - Put the main key first and the tie-break second.
