ぺーぺーSEのテックブログ

備忘録用メモサイト

RSSを購読する

Golangのソート

Golang におけるソートについてまとめる。

  • sort パッケージ
  • sort パッケージで独自のソートを作ってみる
  • スクラッチでソートしてみる

sort パッケージ

sort パッケージでは、以下の Interface に合わせた実装をしておけば、独自の type でも sort.Sort(data Interface) でソートしてくれる。

1
2
3
4
5
type Interface interface {
Len() int // 要素数
Less(i, j int) bool // i 番目の要素が j 番目の要素より小さくなる条件
Swap(i, j int) // i 番目の要素と j 番目の要素を入れ替えるロジック
}

とはいえ面倒なので、IntSlice[]int )、Float64Slice[]float64 )、StringSlice[]string )は用意されており、キャストして使用できる。

1
2
var a []int
sort.Sort(sort.IntSlice(a))

キャストしたら、メンバに Sort() メソッドも実装されている。

1
2
var a []int
sort.IntSlice(a).Sort()

もしくはキャストしなくとも、Ints([]int)Float64s([]float64)Strings([]string) が用意されている。

1
2
var a []int
sort.Ints(a)

Slice

Interface の実装が面倒なら less だけ実装すればよい関数もある。

  • func Slice(slice interface{}, less func(i, j int) bool)
  • func SliceStable(slice interface{}, less func(i, j int) bool)

slice はソート対象。 また、 SliceStable安定ソート

sort パッケージで独自のソートを作ってみる

Interface の実装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package main

import (
"fmt"
"sort"
)

type user struct {
name string
age int
}

type users []user

func (u users) Len() int {
return len(u)
}

func (u users) Less(i, j int) bool {
return u[i].age < u[j].age
}

func (u users) Swap(i, j int) {
u[i], u[j] = u[j], u[i]
}

func main() {
list := []user{
user{name: "A", age: 2},
user{name: "B", age: 1},
user{name: "C", age: 4},
user{name: "D", age: 3},
}
us := users(list)
sort.Sort(us)
fmt.Println(us)
}

Sliceの利用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
"fmt"
"sort"
)

type user struct {
name string
age int
}

func main() {
list := []user{
user{name: "A", age: 2},
user{name: "B", age: 1},
user{name: "C", age: 4},
user{name: "D", age: 3},
}
sort.Slice(list, func(i, j int) bool {
return list[i].age < list[j].age
})
fmt.Println(list)
}

スクラッチでソートしてみる

sort パッケージ使わずに。

バブルソート

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import (
"fmt"
)

func sort(list []int) {
eNum := len(list)
for i := eNum; i > 0; i-- {
for j := 0; j < i-1; j++ {
if list[j] > list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
}
}
}
}

func main() {
list := []int{3, 4, 1, 2, 8, 5}
sort(list)
fmt.Println(list)
}

暇になったら他にも作ろうかなー。