Goでソート

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

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

sort パッケージ

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

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

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

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

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

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

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

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 の実装

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の利用

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 パッケージ使わずに。

バブルソート

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)
}

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