Insertion sort

According to the idea of insert sort, we can easily do insert sort as follows.

func insertionSort(data []int) {
    lo, hi := 0.len(data)
    for i := lo + 1; i < hi; i++ {
        for j := i; j > lo && data[j] < data[j- 1]; j-- {
            data[j], data[j- 1] = data[j- 1], data[j]
        }
    }
}
Copy the code

We can verify that there is no problem.

package main

import (
    "fmt"
)

func main(a)  {
    nums := []int{2.3.4.1.7.9.10.21.17}
    insertionSort(nums)
    fmt.Println(nums)
}
Copy the code

The code output is, and the result is correct

[1 2 3 4 7 9 10 17 21]
Copy the code

The problem

Ok, now the problem is that Go is known to be a static language, which means that different data types can make the above insertion sort unavailable. For example, one day a product wants to support uint32 insertion sort. Well, it’s very simple, just Ctrl+ C + Ctrl+ C to change it a little bit.

func insertionSortUint32(data []uint32) {
    lo, hi := 0.len(data)
    for i := lo + 1; i < hi; i++ {
        for j := i; j > lo && data[j] < data[j- 1]; j-- {
            data[j], data[j- 1] = data[j- 1], data[j]
        }
    }
}
Copy the code

Who knows when the product gets crazy and wants to support float32 insert sort, it might have to add a few more lines of code.

func insertionSortFloat32(data []float32) {
    lo, hi := 0.len(data)
    for i := lo + 1; i < hi; i++ {
        for j := i; j > lo && data[j] < data[j- 1]; j-- {
            data[j], data[j- 1] = data[j- 1], data[j]
        }
    }
}
Copy the code

We know there are more than three types of Go. Will it explode? It doesn’t matter, we have powerful ides that can be implemented quickly. 😏 😏 😏

All right, just kidding. If we were to provide a library form and the user needed a type, we would have to add a type support, and then there would be no problem 😂

To solve

First of all, going back to the three types of sorting in the appeal, we can see that these sorts are basically the same except for the data type. If we want to have a function that supports all data types, do we have to use interfaces to do that? But the interface does not support operations, if the assertion, it is as troublesome as before. Let’s look at the parts of the code where we need to perform operations on the data.

Len (data), data[j] < data[j-1], data[j], data[j-1] = data[j-1], data[j]. Wouldn’t that solve my problem if WE let interface implement these three methods? Now let’s modify our insertion sort with this idea. The code is as follows,

type Data interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)}func insertionSort(data Data) {
    lo, hi := 0, data.Len()
    for i := lo + 1; i < hi; i++ {
        for j := i; j > lo && data.Less(j, j- 1); j-- {
            data.Swap(j, j- 1)}}}Copy the code

Instead of writing dead data types, we use interfaces. If used, the caller simply implements the Data interface.

package main

import (
    "fmt"
)

type Uint32Slice []uint32

func (u Uint32Slice) Len(a) int {return len(u)}
func (u Uint32Slice) Less(i, j int) bool {return u[i] < u[j]}
func (u Uint32Slice) Swap(i, j int) {u[i], u[j] = u[j], u[i]}

type Float32Slice []float32

func (u Float32Slice) Len(a) int {return len(u)}
func (u Float32Slice) Less(i, j int) bool {return u[i] < u[j]}
func (u Float32Slice) Swap(i, j int) {u[i], u[j] = u[j], u[i]}


func main(a)  {
    nums := Uint32Slice{2.3.4.1.7.9.10.21.17}
    insertionSort(nums)
    fmt.Println(nums)

    float32Nums := Float32Slice{2.3.4.1.7.9.10.21.17}
    insertionSort(float32Nums)
    fmt.Println(float32Nums)
}
Copy the code

It can be verified and the results are fine.

[1 2 3 4 7 9 10 21 17]Copy the code

conclusion

We implement an insert sort that supports multiple Data types through the interface. Callers only need to implement the Data interface to use it, without modifying the original function definition of insert sort. This makes our code more abstract and flexible, and interfaces are the answer when faced with similar requirements.