# golang's solution for sorting custom types

• 2020-06-12 09:17:52
• OfStack

preface

The Go language allows us to customize types, and in real projects, we often need to sort by a field of a struct type. I didn't know how to solve this problem before. Later, I searched related problems on the Internet and found some good solutions. Please refer to here and make a summary.

Since the golang sort package itself provides the functionality, there is no need to build a wheel, so let's see how to use the sort package.

sort package, discussion

The sort package of sorting algorithm is also implemented in golang. The sort package internally implements four basic sorting algorithms: insertion sort (insertionSort), merge sort (symMerge), heap sort (heapSort) and quick sort (quickSort). The sort package automatically selects the best sorting algorithm based on actual data.

So we only need to think about the implementation when we write code `sort.Interface` This type will do.

Take a quick look at the sort package

``````
func Sort(data Interface) {
// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSort(data, 0, n, maxDepth)
}
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
//  Internally implemented 4 Sorting algorithm
//  Insertion sort
func insertionSort(data Interface, a, b int)
//  Heap sort
func heapSort(data Interface, a, b int)
//  Quick sort
func quickSort(data Interface, a, b, maxDepth int)
//  Merge sort
func symMerge(data Interface, a, m, b int)``````

So I'm gonna call `sort.Sort()` To implement custom type sorting, we only need our type to implement the three methods in the Interface interface type.

Take a look at the sort package itself for example `[]int ` How types are sorted

``````
//  First of all, I've defined 1 a []int Alias of a type IntSlice
type IntSlice []int
func (p IntSlice) Len() int   { return len(p) }
//  Compare the two element sizes   ascending
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
//  Exchange data
func (p IntSlice) Swap(i, j int)  { p[i], p[j] = p[j], p[i] }
// sort.Ints() Internal calls Sort()  Method implementation ordering
//  Pay attention to   The first []int  convert  IntSlice type   Because of this type is implemented Interface the 3 A method of
func Ints(a []int) { Sort(IntSlice(a)) }``````

Let's follow suit and sort our custom structure types in descending order

``````
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type Persons []Person
func (p Persons) Len() int { return len(p) }
func (p Persons) Less(i, j int) bool {
return p[i].Age > p[j].Age
}
//  Exchange data
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func main() {
persons := Persons{
{
Name: "test1",
Age: 20,
},
{
Name: "test2",
Age: 22,
},
{
Name: "test3",
Age: 21,
},
}
fmt.Println(" Before ordering ")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
sort.Sort(persons)
fmt.Println(" After ordering ")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
}``````

Actually, one is the same `Len()` and `Swap() ` Basically nothing is changed, only the comparison of elements is involved `Less() ` The approach will change.

What do we do when we sort more than one field in a structure? Do we write these three methods for every one sorted? Of course not. We can solve this problem with nested constructs. Because a nested structure can inherit all the properties and methods of a parent structure

For example, if I want to sort the Name field and Age pair of Person above, we can use nested constructs to improve 1.

``````
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type Persons []Person
// Len() Methods and Swap() The method does not change
func (p Persons) Len() int { return len(p) }
//  Exchange data
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
//  Nested structures   Will inherit  Person  All properties and methods
//  So it's equivalent to SortByName  Also achieved  Len()  and  Swap()  methods
type SortByName struct{ Persons }
//  Sort by the name length of the element in descending order   (Follow your own business logic here)
func (p SortByName) Less(i, j int) bool {
return len(p.Persons[i].Name) > len(p.Persons[j].Name)
}
type SortByAge struct{ Persons }
func (p SortByAge) Less(i, j int) bool {
return p.Persons[i].Age > p.Persons[j].Age
}
func main() {
persons := Persons{
{
Name: "test123",
Age: 20,
},
{
Name: "test1",
Age: 22,
},
{
Name: "test12",
Age: 21,
},
}
fmt.Println(" Before ordering ")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
sort.Sort(SortByName{persons})
fmt.Println(" After ordering ")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
}``````

conclusion

Related articles: