Problem overview
Go can sort numbers and strings on its own because it knows which of two of them comes first. For a struct of your own, it doesn't, until you say how two of them compare. Once you have, the standard sort package can sort a slice of those structs with no comparison written at the call.
You write a Student struct, created by NewStudent(name, grade), and a function rankStudents(students) that sorts the students and returns their names in order. A student comes first if their grade is higher. When two grades are equal, the name that comes first alphabetically comes first. 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.
Approach
Go has no comparison operators or methods for structs. Instead, sort.Sort accepts any value that has three methods, which together make up sort.Interface:
Len()returns how many elements there are.Less(i, j)says whether elementimust come before elementj.Swap(i, j)exchanges two elements.
The sort calls them as often as it needs; you write no sorting loop. You attach the methods to a named slice type, here ByRank, defined as []Student. All the ranking rules live in Less.
Step by step
- Give
Studenttwo fields,nameandgrade, and writeNewStudentto return one with both set. Lenreturnslen(this), sincethisis the slice itself.- In
Less(i, j), first check whether the grades differ. If they do, return whether studenti's grade is greater than studentj's, because a higher grade ranks first. - If the grades are equal, return whether student
i's name is less than studentj's. Strings compare letter by letter, so equal grades go from A to Z. Swapexchanges the two elements in one assignment:this[i], this[j] = this[j], this[i]. Go evaluates the right side first, so no temporary variable is needed.- In
rankStudents, callsort.Sort(ByRank(students)). The conversionByRank(students)views the same slice as aByRank, so the sort reordersstudentsitself. - Then collect the names into a new
[]string, withappend, in the sorted order, and return it.
The solution in Go
type Student struct {
name string
grade int
}
func NewStudent(name string, grade int) Student {
return Student{name: name, grade: grade}
}
type ByRank []Student
func (this ByRank) Len() int {
return len(this)
}
func (this ByRank) Less(i, j int) bool {
if this[i].grade != this[j].grade {
return this[i].grade > this[j].grade
}
return this[i].name < this[j].name
}
func (this ByRank) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}
func rankStudents(students []Student) []string {
sort.Sort(ByRank(students))
names := []string{}
for _, student := range students {
names = append(names, student.name)
}
return names
}A few details:
- The method names
Len,LessandSwapstart with capital letters becausesort.Interfacenames them that way. Your own methods elsewhere may start lowercase. - Nothing says that
ByRankimplementssort.Interface. Having the three methods is enough. sort.Sortchanges the slice you pass, so afterrankStudents(students)the caller's slice is sorted too. The function returns the names only.
Trying it
students := []Student{NewStudent("Ana", 90), NewStudent("Bob", 85), NewStudent("Cid", 90)}
ranked := ByRank(students)
fmt.Println(ranked.Len(), ranked.Less(0, 1), ranked.Less(1, 0), ranked.Less(0, 2), ranked.Less(2, 0))
fmt.Println(rankStudents(students))
fmt.Println(students)3 true false true false
[Ana Cid Bob]
[{Ana 90} {Cid 90} {Bob 85}]
On the first line, Ana (index 0) comes before Bob (index 1) but not the other way round, and Ana comes before Cid (index 2) but not the other way round: the names decide the tie. The last line shows that the original slice is now in ranked order.
Complexity
The sort makes O(n log n) calls to Less for n students, and each call takes constant time, since it compares an integer and, at most, two short names. Building the names list is O(n) more.
Edge cases and common mistakes
- Direction of the grade test. A higher grade comes first, so the test is
>, not<. Reversing it ranks the worst student first. - Tie-break direction. Names go from A to Z, so the name test is
<. For Max, Leo, Anna and Ann with the same grade 88, the result is[Ann Anna Leo Max]: when one name is the start of the other, the shorter one is smaller, so"Ann" < "Anna"is true. - Capitals. Strings compare by byte values, and capital letters sort before lowercase ones. The names here are one capital followed by lowercase letters, so the comparison works as expected.
- Less must be strict. It should return false for two equal elements. Here no two students share a name, so it never matters.
- Different grades. For Eve 55, Dan 100, Bea 0 and Cal 99 the names never matter, and the result is
[Dan Cal Eve Bea].
Another way
For a one-off sort, sort.Slice takes just a comparison function and needs no named type:
sort.Slice(students, func(i, j int) bool {
if students[i].grade != students[j].grade {
return students[i].grade > students[j].grade
}
return students[i].name < students[j].name
})It gives the same order. This lesson uses ByRank because defining the ordering once on a type means every sort of that kind of slice uses the same rule.
Testing
Check three kinds of input. A list where all the grades differ (Eve 55, Dan 100, Bea 0, Cal 99) tests the grade rule alone. A list with one shared grade (Max, Leo, Anna and Ann at 88) tests the name rule alone, including the shorter-name case. The mixed list, Ana 90, Bob 85, Cid 90, tests both together. Also try a single student: Len returns 1, the sort has nothing to compare, and the one name comes back. Because sort.Sort isn't stable, equal elements may swap places, which is why the name tie-break matters: it leaves no two students equal.
