Problem overview
A list of numbers or strings sorts itself, because C# knows which of two of them comes first. For objects of your own class it does not, until the class says so. Here the class is Student, created with Student(name, grade). A student comes first when the grade is higher; when two grades are equal, the name that comes first alphabetically comes first. RankStudents(students) sorts the list with its own Sort() and returns the names in that order.
For Ana 90, Bob 85 and Cid 90 the result is Ana Cid Bob: Ana and Cid tie on 90 and Ana's name comes first, and Bob is last.
Approach: teach the class to compare itself
C#'s List<T>.Sort() with no arguments looks for the interface IComparable<T>. The interface has one method, CompareTo(other), which returns:
- a negative number if this object comes first;
- a positive number if
othercomes first; - 0 if they are equal.
Once Student says : IComparable<Student> and provides that method, no sorting loop and no comparison at the call is needed.
Step by step
- Give
Studenttwo public fields,string nameandint grade, and store the constructor's parameters in them withthis.. - In
CompareTo, if the grades differ, returnother.grade - grade. Higher grades must come first, and when this student's grade is bigger the subtraction is negative, which means "this one first". - If the grades are equal, return
name.CompareTo(other.name). Strings already compare alphabetically, with a negative result whennamecomes first. - In
RankStudents, callstudents.Sort(), create aList<string>, add each sorted student'snamein aforeachloop and return it.
The solution in C#
class Student : IComparable<Student> {
public string name;
public int grade;
public Student(string name, int grade) {
this.name = name;
this.grade = grade;
}
public int CompareTo(Student other) {
if (grade != other.grade) {
return other.grade - grade;
}
return name.CompareTo(other.name);
}
}
class Solution {
public List<string> RankStudents(List<Student> students) {
students.Sort();
List<string> names = new List<string>();
foreach (Student student in students) {
names.Add(student.name);
}
return names;
}
}Details worth knowing
The sign is what matters. Sort() only looks at whether the result is negative, zero or positive. Comparing Ana (90) with Bob (85) returns -5, comparing Bob with Ana returns 5, and comparing two students with the same name and grade returns 0.
The order of the subtraction is the whole trick. other.grade - grade sorts from high to low. Writing grade - other.grade would put the lowest grade first. For names, the order is the natural one, name.CompareTo(other.name), A to Z.
Prefixes. "Ann".CompareTo("Anna") is negative, so when one name is the start of the other, the shorter name comes first. Four students with grade 88 named Max, Leo, Anna and Ann come out as Ann Anna Leo Max.
Subtracting is safe here because the grades are between 0 and 100. With arbitrary integers a subtraction can overflow, and other.grade.CompareTo(grade) would be the safer form.
Testing
Results of RankStudents:
Ana 90, Bob 85, Cid 90 -> Ana Cid Bob
Eve 55, Dan 100, Bea 0, Cal 99 -> Dan Cal Eve Bea
Max 88, Leo 88, Anna 88, Ann 88 -> Ann Anna Leo MaxComplexity
The sort makes O(n log n) comparisons for n students and each comparison takes constant time. The loop that builds the names is O(n). Together this is O(n log n) time, with O(n) extra space for the list of names.
Tracing the first example
The sort asks the students to compare themselves with each other. Some of the comparisons for Ana 90, Bob 85 and Cid 90:
| Call | Result | Meaning |
|---|---|---|
| Ana.CompareTo(Cid) | -1 | equal grades, "Ana" is before "Cid": Ana first |
| Cid.CompareTo(Bob) | -5 | 90 is higher than 85: Cid first |
| Bob.CompareTo(Ana) | 5 | Ana is higher: Ana first |
The sorted list is Ana, Cid, Bob. Without calling Sort(), the list stays in the order it was built, Ana Bob Cid.
Another way: a comparison at the call
Sort also accepts a comparison function, which is useful when you cannot change the class or want a second order:
students.Sort((p, q) => q.grade != p.grade
? q.grade - p.grade
: string.CompareOrdinal(p.name, q.name));On the first example this gives Ana Cid Bob too. The lesson asks for the class itself to know its order, though, so that a plain Sort() works anywhere. LINQ gives the same result with OrderByDescending(s => s.grade).ThenBy(s => s.name), and it returns a new sequence instead of sorting the list in place.
Common mistakes
- Forgetting
IComparable<Student>. Without it,Sort()cannot compare two students. For a class with no comparison, a call toSort()throwsInvalidOperationExceptionwith the message "Failed to compare two elements in the array." - Reversing the subtraction and getting the grades in ascending order.
- Comparing the names first, or only the names.
- Writing your own sorting loop instead of letting
Sort()useCompareTo.
Why the names are compared with CompareTo
Strings already know how to compare themselves: "Ana".CompareTo("Cid") is negative, so the tie-breaker needs no extra code. Names in this lesson are a capital letter followed by lowercase letters, so the default comparison puts them in the order a person would expect. Notice also that no two students share a name, which means two different students are never "equal" for the sort, and the final order is fully decided.
Key takeaways
- To make your own class sortable with a plain
Sort(), implementIComparable<T>and itsCompareTo. - The result's sign is its meaning: negative for "me first", positive for "the other first", 0 for equal.
- For a tie-breaker, compare the main key first, and only when it is equal compare the second one.
- Comparing neighbours in the returned list, as the lesson's tests do, is a good way to check your own
CompareTo: for each pair of neighbours the first must not come after the second.
