Go sortパッケージ Walkthrough

sort パッケージについて

sort package は、slice のソートに関するプリミティブを提供しています。

$ gocloc --not-match=test sort
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Go                               6            241            530           1314
-------------------------------------------------------------------------------
TOTAL                            6            241            530           1314
-------------------------------------------------------------------------------

Find/Search

Find

func Find(n int, cmp func(int) int) (I int, found bool)

sort.Searchメソッドが使いにくいという意見から取り入れられました。

https://github.com/golang/go/issues/50340#issuecomment-1016736447

バイナリサーチ（二分探索）を使用して、一致する最小の index を返します。
バイナリサーチを利用するためスライスはソート済みである必要があります。

x := []byte("abcdefghi")
target := []byte("e")
i, found := sort.Find(len(x), func(i int) int {
    return bytes.Compare(target, x[i:i+1])
})
if found {
    fmt.Printf("found %s at entry %d\n", target, i)
} else {
    fmt.Printf("%s not found, would insert at %d", target, i)
}
// found e at entry 4

Search

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

バイナリサーチを使用して、f が true になる最小の index を返します。

s := []int{1, 2, 3, 4, 5, 6}
i := sort.Search(len(s), func(i int) bool { return s[i] >= 4 })
fmt.Println(i)
// 3

float64,int,string の Search 関数のラッパーが提供されています。

Slice/Sort

Slice

func Slice(x any, less func(I, j int) bool)

スライスを less 関数でソートします。

内部的には Pattern-defeating Quicksort というアルゴリズムが使用されています。
詳細はこちらの記事が分かりやすいです。
Go1.19 に採用された Pattern-defeating Quicksort の紹介 - エムスリーテックブログ

安定したソートを行う場合はSliceStableが利用できます。

Less 関数は Interface タイプの Less を満たす必要があります。

Int > Less: https://cs.opensource.google/go/go/+/refs/tags/go1.20:src/sort/sort.go;l=115
Float > Less: https://cs.opensource.google/go/go/+/refs/tags/go1.20:src/sort/sort.go;l=133
String > Less: https://cs.opensource.google/go/go/+/refs/tags/go1.20:src/sort/sort.go;l=148

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].Name < people[j].Name })
fmt.Println("By name:", people)

sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println("By age:", people)
// By name: [{Alice 55} {Bob 75} {Gopher 7} {Vera 24}]
// By age: [{Gopher 7} {Vera 24} {Alice 55} {Bob 75}]