Golang standard library: sort package – sorting algorithm

3.1 sort – sorting algorithm

This package implements four basic sorting algorithms: insertion sort, merge sort, heap sort, and quick sort.
But these four sorting methods are not public, they are only used internally by the sort package. Therefore, when sorting a data set, you do not need to consider which sorting method should be selected, as long as the three methods defined by sort.Interface are implemented: the Len() method to obtain the length of the data set, the Less() method to compare the sizes of two elements, and By exchanging the positions of two elements with the Swap() method, the data collection can be sorted smoothly. The sort package automatically selects an efficient sorting algorithm based on the actual data.
In addition, in order to facilitate the operation of common data types, the sort package provides complete support for []int slicing, []float64 slicing and []string slicing, mainly including:

• Sorting support for slices of basic data types
• Basic data element lookup
• Determine whether basic data type slices have been sorted
• Reverse the sorted data set

3.1.1 Data collection sorting

As mentioned earlier, sorting data collections (including collections of custom data types) requires implementing the three methods of the sort.Interface interface. Let’s look at the definition of this interface below:

type Interface interface {<!-- -->
// Get the number of elements in the data collection
Len() int
// If the data at index i is less than the data at index j, return true and the following Swap() will not be called, that is, the data is sorted in ascending order.
Less(i, j int) bool
// Swap the positions of the two elements indexed by i and j
        Swap(i, j int)
}

After the data collection implements these three methods, it can call the Sort() method of the package for sorting.
The Sort() method is defined as follows:

func Sort(data Interface)

The only parameter of the Sort() method is the data collection to be sorted.

The package also provides a method to determine whether the data collection has been sorted. The internal implementation of this method relies on our own implementation of the Len() and Less() methods:

func IsSorted(data Interface) bool {<!-- -->
    n := data.Len()
    for i := n - 1; i > 0; i-- {<!-- -->
        if data.Less(i, i-1) {<!-- -->
            return false
        }
    }
    return true
}

Here is an example of using the sort package to sort student grades:

package main

import (
"fmt"
"sort"
)

//Student grade structure
type StuScore struct {<!-- -->
    name string // name
    score int // score
}

typeStuScores[]StuScore

//Len()
func (s StuScores) Len() int {<!-- -->
returnlen(s)
}

//Less(): Scores will be sorted from low to high
func (s StuScores) Less(i, j int) bool {<!-- -->
return s[i].score < s[j].score
}

//Swap()
func (s StuScores) Swap(i, j int) {<!-- -->
s[i], s[j] = s[j], s[i]
}

func main() {<!-- -->
    stus := StuScores{<!-- -->
                {<!-- -->"alan", 95},
                {<!-- -->"hikerell", 91},
                {<!-- -->"acmfly", 96},
                {<!-- -->"leao", 90},
}
\t\t\t\t
//Print unsorted stus data
    fmt.Println("Default:\
\t",stus)
    //StuScores has implemented the sort.Interface interface, so you can call the Sort function for sorting
sort.Sort(stus)
// Determine whether the order has been sorted, and true will be printed.
fmt.Println("IS Sorted?\
\t", sort.IsSorted(stus))
//Print the sorted stus data
    fmt.Println("Sorted:\
\t",stus)
}

The sample program’s custom type StuScores implements the sort.Interface interface, so its object can be passed in as a parameter to sort.Sort() and sort.IsSorted(). operation result:

Default:
     [{<!-- -->alan 95} {<!-- -->hikerell 91} {<!-- -->acmfly 96} {<!-- -->leao 90}]
IS Sorted?
     true
Sorted:
     [{<!-- -->leao 90} {<!-- -->hikerell 91} {<!-- -->alan 95} {<!-- -->acmfly 96}]

This example implements ascending sorting. If you want to get the descending sorting result, you only need to modify the Less() function:

//Less(): Sort the results in descending order, only change the less than sign to the greater than sign
func (s StuScores) Less(i, j int) bool {<!-- -->
return s[i].score > s[j].score
}

In addition, the sort package provides the Reverse() method, which allows data to be sorted in reverse order according to the sorting method defined by Less() without having to modify the Less() code. The method is defined as follows:

func Reverse(data Interface) Interface

We can see a sort.Interface interface type returned by Reverse(). The internal implementation of the entire Reverse() is quite interesting:

// Defines a reverse structure type and embeds the Interface interface
type reverse struct {<!-- -->
    Interface
}

//reverse Less() method of structure type has the opposite behavior of embedded Less() method
//Len() and Swap() methods will maintain the method behavior of the embedded type
func (r reverse) Less(i, j int) bool {<!-- -->
    return r.Interface.Less(j, i)
}

// Return the new data type that implements the Interface interface
func Reverse(data Interface) Interface {<!-- -->
    return & amp;reverse{<!-- -->data}
}

After understanding the internal principles, you can use Reverse() in the student grade sorting example to achieve ascending grade sorting:

sort.Sort(sort.Reverse(stus))
fmt.Println(stus)

The last method: Search()

func Search(n int, f func(int) bool) int

This method uses the “binary search” algorithm to find the smallest value i such that f(x)(0<=x Prerequisite: f(x)(0<=x If there is no i for which f(i) returns true, then n is returned.

A common way to use the Search() function is to search whether element x is in a slice s that has been sorted in ascending order:

x := 11
s := []int{<!-- -->3, 6, 8, 11, 45} // Note that it has been sorted in ascending order
pos := sort.Search(len(s), func(i int) bool {<!-- --> return s[i] >= x })
if pos < len(s) & amp; & amp; s[pos] == x {<!-- -->
    fmt.Println(x, "The position in s is: ", pos)
} else {<!-- -->
    fmt.Println("s does not contain elements ", x)
}

The official documentation also provides a small program for guessing numbers:

func GuessingGame() {<!-- -->
vars string
fmt.Printf("Pick an integer from 0 to 100.\
")
answer := sort.Search(100, func(i int) bool {<!-- -->
fmt.Printf("Is your number <= %d? ", i)
fmt.Scanf("%s", & amp;s)
return s != "" & amp; & s[0] == 'y'
})
fmt.Printf("Your number is %d.\
", answer)
}

3.1.2 Internal data type sorting already supported by the sort package

As mentioned earlier, the sort package natively supports the sorting operations of three built-in data type slices []int, []float64 and []string, that is, we do not need to implement the relevant Len() and Less ourselves. () and Swap() methods.

1. IntSlice type and []int sorting

Since the internal implementation and usage of []int slice sorting are similar to []float64 and []string, only this part is described in detail.

The sort package defines an IntSlice type and implements the sort.Interface interface:

type IntSlice []int
func (p IntSlice) Len() int {<!-- --> return len(p) }
func (p IntSlice) Less(i, j int) bool {<!-- --> return p[i] < p[j] }
func (p IntSlice) Swap(i, j int) {<!-- --> p[i], p[j] = p[j], p[i] }
//The IntSlice type defines the Sort() method and wraps the sort.Sort() function
func (p IntSlice) Sort() {<!-- --> Sort(p) }
//The IntSlice type defines the SearchInts() method and wraps the SearchInts() function
func (p IntSlice) Search(x int) int {<!-- --> return SearchInts(p, x) }

And the provided sort.Ints() method uses the IntSlice type:

func Ints(a []int) {<!-- --> Sort(IntSlice(a)) }

Therefore, it is more common to sort []int slices using sort.Ints() rather than using the IntSlice type directly:

s := []int{<!-- -->5, 2, 6, 3, 1, 4} // Unsorted slice data
sort.Ints(s)
fmt.Println(s) // will output [1 2 3 4 5 6]

If you want to use descending sorting, you obviously need to use the Reverse() method mentioned earlier:

s := []int{<!-- -->5, 2, 6, 3, 1, 4} // Unsorted slice data
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s) // will output [6 5 4 3 2 1]

If you want to find the position of the integer x in slice a, compared to the previously mentioned Search() method, the sort package provides SearchInts():

func SearchInts(a []int, x int) int

Note that the conditions for using SearchInts() are: Slice a has been sorted in ascending order The following is an example of incorrect use:

s := []int{<!-- -->5, 2, 6, 3, 1, 4} // Unsorted slice data
fmt.Println(sort.SearchInts(s, 2)) // will output 0 instead of 1

2. Float64Slice type and []float64 sorting

The implementation is similar to Ints, just look at its internal implementation:

type Float64Slice []float64

func (p Float64Slice) Len() int {<!-- --> return len(p) }
func (p Float64Slice) Less(i, j int) bool {<!-- --> return p[i] < p[j] || isNaN(p[i]) & amp; & amp; !isNaN(p [j]) }
func (p Float64Slice) Swap(i, j int) {<!-- --> p[i], p[j] = p[j], p[i] }
func (p Float64Slice) Sort() {<!-- --> Sort(p) }
func (p Float64Slice) Search(x float64) int {<!-- --> return SearchFloat64s(p, x) }

Three methods corresponding to Sort(), IsSorted(), and Search():

func Float64s(a []float64)
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int

It should be noted that in the Less method defined above by the Float64Slice type, there is an internal function isNaN().
The implementation of isNaN() and IsNaN() in the math package is exactly the same. The reason why the sort package does not use math.IsNaN() is entirely based on package dependency considerations. It should be As you can see, the implementation of the sort package does not depend on any other package.

3. StringSlice type and []string sorting

Size comparison between two string objects is based on “lexicographic order”.

The implementation is similar to Ints, just look at its internal implementation:

type StringSlice []string

func (p StringSlice) Len() int {<!-- --> return len(p) }
func (p StringSlice) Less(i, j int) bool {<!-- --> return p[i] < p[j] }
func (p StringSlice) Swap(i, j int) {<!-- --> p[i], p[j] = p[j], p[i] }
func (p StringSlice) Sort() {<!-- --> Sort(p) }
func (p StringSlice) Search(x string) int {<!-- --> return SearchStrings(p, x) }

Three methods corresponding to Sort(), IsSorted(), and Search():

func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int

3.1.3 []interface sorting and search

From the previous content, we can know that as long as the sort.Interface interface is implemented, sorting, searching and other operations can be completed through the functions in the sort package. And the sort package has helped us implement this interface for the three types of []int, []float64, and []string. We can Convenient to call. However, this usage is not friendly to slices of other data types. We may need to define a separate []struct type for a large number of structs, and then implement the sort.Interface interface for it, similar to this:

type Person struct {<!-- -->
    Name string
    Age int
}
type Persons []Person

func (p Persons) Len() int {<!-- -->
    panic("implement me")
}

func (p Persons) Less(i, j int) bool {<!-- -->
    panic("implement me")
}

func (p Persons) Swap(i, j int) {<!-- -->
    panic("implement me")
}

Think about a question: Why can the sort package sort []int but not []struct?

Because sorting involves comparing the values of two variables, and a struct may contain multiple attributes, the program does not know which attribute or attributes you want to use as a measure of size. If you can help the program complete the comparison and return the results, the methods in the sort package can complete sorting, judgment, search, etc. The sort package provides the following functions:

func Slice(slice interface{<!-- -->}, less func(i, j int) bool)
func SliceStable(slice interface{<!-- -->}, less func(i, j int) bool)
func SliceIsSorted(slice interface{<!-- -->}, less func(i, j int) bool) bool
func Search(n int, f func(int) bool) int

As can be seen from the function signature, the three functions related to sorting all receive []interface, and a comparison function needs to be passed in to compare the sizes of two variables for the program, because the function signature and function Because of the domain, this function can only be an anonymous function.

1. sort.Slice

This function completes the sorting of []interface. For example:

people := []struct {<!-- -->
Name string
Age int
}{<!-- -->
{<!-- -->"Gopher", 7},
{<!-- -->"Alice", 55},
{<!-- -->"Vera", 24},
{<!-- -->"Bob", 75},
}

sort.Slice(people, func(i, j int) bool {<!-- --> return people[i].Age < people[j].Age }) // Sort by age in ascending order
fmt.Println("Sort by age:", people)

Output result:

By age: [{<!-- -->Gopher 7} {<!-- -->Vera 24} {<!-- -->Alice 55} {<!-- -->Bob 75 }]

2. sort.SliceStable

This function completes the stable sorting of []interface. For example:

people := []struct {<!-- -->
Name string
Age int
}{<!-- -->
{<!-- -->"Gopher", 7},
{<!-- -->"Alice", 55},
{<!-- -->"Vera", 24},
{<!-- -->"Bob", 75},
}

sort.SliceStable(people, func(i, j int) bool {<!-- --> return people[i].Age > people[j].Age }) // Sort by age in descending order
fmt.Println("Sort by age:", people)

Output result:

By age: [{<!-- -->Bob 75} {<!-- -->Alice 55} {<!-- -->Vera 24} {<!-- -->Gopher 7 }]

3. sort.SliceIsSorted

This function determines whether []interface is ordered. For example:

people := []struct {<!-- -->
    Name string
    Age int
}{<!-- -->
    {<!-- -->"Gopher", 7},
    {<!-- -->"Alice", 55},
    {<!-- -->"Vera", 24},
    {<!-- -->"Bob", 75},
}

sort.Slice(people, func(i, j int) bool {<!-- --> return people[i].Age > people[j].Age }) // Sort by age in descending order
fmt.Println("Sort by age:", people)
fmt.Println("Sorted:",sort.SliceIsSorted(people,func(i, j int) bool {<!-- --> return people[i].Age < people[j].Age }))

Output result:

Sort by age: [{<!-- -->Bob 75} {<!-- -->Alice 55} {<!-- -->Vera 24} {<!-- -->Gopher 7}]
Sorted: false

The sort package does not provide a reverse order function for the []interface, but as can be seen from 1 and 2, the comparison function we passed in has determined whether the sorting result is in ascending or descending order.

Determining whether the slice is ordered also depends on the comparison function we pass in. As can be seen from 3, although the slice has been sorted in descending order by age, the comparison function we give when judging whether the slice is ordered is to judge whether it is Sorted in ascending order, so the final result is false.

4. sort.Search

This function determines whether the specified element exists in []interface. For example:

• Ascending slice

The Search function provided by the sort package for []int, []float64, []string is actually called, because this function is The binary search method is used, so the slice is required to be sorted in ascending order. And the judgment condition must be >=, which is also the way to write the three search related functions provided by the official library.

Give a chestnut:

a := []int{<!-- -->2, 3, 4, 200, 100, 21, 234, 56}
x := 21

sort.Slice(a, func(i, j int) bool {<!-- --> return a[i] < a[j] }) // Sort in ascending order
index := sort.Search(len(a), func(i int) bool {<!-- --> return a[i] >= x }) // Find elements

if index < len(a) & amp; & amp; a[index] == x {<!-- -->
fmt.Printf("found %d at index %d in %v\
", x, index, a)
} else {<!-- -->
fmt.Printf("%d not found in %v,index:%d\
", x, a, index)
}

Output result:

found 21 at index 3 in [2 3 4 21 56 100 200 234]

• Descending slice

If the slice is in descending order and we don’t want to change it to ascending order, we only need to change the judgment condition from >= to <=. The code will not be given here, and interested students can try it themselves. It is recommended to use ascending order and corresponding judgment conditions to keep the style consistent with the official function.