はじめに
※Go 1.8 以降の場合はsort.Slice,sort.StableSliceを使いましょう。
AtCoder でソートしたかった
AtCoder の問題を解くなかで、独自に定義した型のソートをしたい場面があったので、sort.Sliceを使って実装しました。
ですが、AtCoder に提出するとコンパイルエラーとなりました。
# command-line-arguments
./Main.go:30: undefined: sort.SliceStable
調べてみると、sort.Sliceは1.8 から導入されました。
では、1.8 以前ではどうやってソートを実現していたのだろう？と疑問に思い調べた結果をメモとして残しておきます。
1.8 以前では、sort.Interface を満たすための関数実装が必要
1.8 以前でソートを実現するには sort.Interface 満たすための関数を実装する必要があります。
sort.Interface にはLen,Less,Swapの 3 つの関数が定義されています。
// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
これらを定義することでソートが可能になります。
検証用コード
package main
import (
"fmt"
"sort"
)
type Student struct {
ID int
Height int
}
type Students []Student
func (s Students) Len() int {
return len(s)
}
func (s Students) Less(i, j int) bool {
return s[i].Height > s[j].Height
}
func (s Students) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func main() {
sortSlice()
sortSort()
}
func sortSlice() {
students := []Student{
{ID: 1, Height: 150},
{ID: 2, Height: 170},
{ID: 3, Height: 180},
{ID: 4, Height: 155},
{ID: 5, Height: 180},
}
sort.Slice(students, func(i, j int) bool {
return students[i].Height > students[j].Height
})
fmt.Println("sort.Slice")
for _, s := range students {
fmt.Printf("%+v\n", s)
}
}
func sortSort() {
students := []Student{
{ID: 1, Height: 150},
{ID: 2, Height: 170},
{ID: 3, Height: 180},
{ID: 4, Height: 155},
{ID: 5, Height: 180},
}
sort.Sort(Students(students))
fmt.Println("sort.Sort")
for _, s := range students {
fmt.Printf("%+v\n", s)
}
}