...

パッケージ sort

import "sort"
概要
目次

概要 ▾

sort パッケージは,スライスやユーザーが定義したコレクションをソートするための 基本的な機能を提供します。

コード:

package sort_test

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge は Age フィールドを使って, []Person に
// sort.Interface インターフェースを実装します。
type ByAge []Person

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

func Example() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    // スライスをソートするには 2 つの方法があります。
    // 1 つめに,ByAge のように,スライス型に必要ないくつかのメソッドを実装し,sort.Sort を呼び出します。
    // 最初の例では,このテクニックを使っています。
    sort.Sort(ByAge(people))
    fmt.Println(people)

    // もう一つの方法は,クロージャの Less 関数を用意して,
    // sort.Slice を使います。
    // この場合,メソッドは必要ありません。
    // (メソッドがあったとしても,無視されます。)
    // この例では,ByAge.Less とは逆順にソートしています。
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age > people[j].Age
    })
    fmt.Println(people)

    // Output:
    // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
    // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
    // [John: 42 Bob: 31 Jenny: 26 Michael: 17]
}

例 (SortKeys)

ExampleSortKeys では,ソート方法を指定してソートするテクニックを紹介します。

コード:

package sort_test

import (
    "fmt"
    "sort"
)

// 単位をわかりやすくするための型定義
type earthMass float64
type au float64

// Planet は,太陽系の惑星の特徴を定義します。
type Planet struct {
    name     string
    mass     earthMass
    distance au
}

// By は,Planet の順序を定義する "less" 関数の型です。
type By func(p1, p2 *Planet) bool

// Sort は,関数型 By のメソッドで,関数に従ってスライスをソートします。
func (by By) Sort(planets []Planet) {
    ps := &planetSorter{
        planets: planets,
        by:      by, // Sort メソッドのレシーバはソート順を決める関数(クロージャ)です。
    }
    sort.Sort(ps)
}

// planetSorter は,ソートするための by 関数と Planet のスライスを組み合わせです。
type planetSorter struct {
    planets []Planet
    by      func(p1, p2 *Planet) bool // Less 関数で用いるクロージャ
}

// Len は sort.Interface で必要な関数です。
func (s *planetSorter) Len() int {
    return len(s.planets)
}

// Swap は sort.Interface で必要な関数です。
func (s *planetSorter) Swap(i, j int) {
    s.planets[i], s.planets[j] = s.planets[j], s.planets[i]
}

// Less は sort.Interface で必要な関数です。 by クロージャを呼び出します。
func (s *planetSorter) Less(i, j int) bool {
    return s.by(&s.planets[i], &s.planets[j])
}

var planets = []Planet{
    {"Mercury", 0.055, 0.4},
    {"Venus", 0.815, 0.7},
    {"Earth", 1.0, 1.0},
    {"Mars", 0.107, 1.5},
}

// ExampleSortKeys では,ソート方法を指定してソートするテクニックを紹介します。
func Example_sortKeys() {
    // Planet 構造体をソートするクロージャ。
    name := func(p1, p2 *Planet) bool {
        return p1.name < p2.name
    }
    mass := func(p1, p2 *Planet) bool {
        return p1.mass < p2.mass
    }
    distance := func(p1, p2 *Planet) bool {
        return p1.distance < p2.distance
    }
    decreasingDistance := func(p1, p2 *Planet) bool {
        return distance(p2, p1)
    }

    // 様々な方法で Planet をソートします。
    By(name).Sort(planets)
    fmt.Println("By name:", planets)

    By(mass).Sort(planets)
    fmt.Println("By mass:", planets)

    By(distance).Sort(planets)
    fmt.Println("By distance:", planets)

    By(decreasingDistance).Sort(planets)
    fmt.Println("By decreasing distance:", planets)

    // Output: By name: [{Earth 1 1} {Mars 0.107 1.5} {Mercury 0.055 0.4} {Venus 0.815 0.7}]
    // By mass: [{Mercury 0.055 0.4} {Mars 0.107 1.5} {Venus 0.815 0.7} {Earth 1 1}]
    // By distance: [{Mercury 0.055 0.4} {Venus 0.815 0.7} {Earth 1 1} {Mars 0.107 1.5}]
    // By decreasing distance: [{Mars 0.107 1.5} {Earth 1 1} {Venus 0.815 0.7} {Mercury 0.055 0.4}]
}

例 (SortMultiKeys)

ExampleMultiKeys では,複数のフィールドの様々な組み合わせでソートするテクニックを紹介します。 1 つのフィールドを比較する Less 関数をつなげて, 様々なソートを実現しています。

コード:

package sort_test

import (
    "fmt"
    "sort"
)

// Change は,ソースコードの変更,ユーザ,言語,変更サイズを記録します。
type Change struct {
    user     string
    language string
    lines    int
}

type lessFunc func(p1, p2 *Change) bool

// multiSorter は Sort インターフェースを実装し,changes をソートします。
type multiSorter struct {
    changes []Change
    less    []lessFunc
}

// Sort は引数のスライスを,OrderedBy で指定された less 関数にしたがってソートします。
func (ms *multiSorter) Sort(changes []Change) {
    ms.changes = changes
    sort.Sort(ms)
}

// OrderedBy は less 関数を順番に適用してソートする multiSorter を返します。
// Sort メソッドを呼んでソートします。
func OrderedBy(less ...lessFunc) *multiSorter {
    return &multiSorter{
        less: less,
    }
}

// Len は sort.Interface で必要な関数です。
func (ms *multiSorter) Len() int {
    return len(ms.changes)
}

// Swap は sort.Interface で必要な関数です。
func (ms *multiSorter) Swap(i, j int) {
    ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i]
}

// Less は sort.Interface で必要な関数です。
// 2つの Change で区別がつくまで less 関数を順に呼び出します。
// less 関数を毎回,2回呼び出す可能性があることに注意してください。
// less 関数が -1, 0, 1 を返すように設計すれば,
// 呼び出し回数を減らして効率をあげることができます。
// どうぞ練習問題として挑戦してみてください。
func (ms *multiSorter) Less(i, j int) bool {
    p, q := &ms.changes[i], &ms.changes[j]
    // 最後を除くすべての比較を行います。
    var k int
    for k = 0; k < len(ms.less)-1; k++ {
        less := ms.less[k]
        switch {
        case less(p, q):
            // p < q, それで,結果を返せます。
            return true
        case less(q, p):
            // p > q, それで,結果を返せます。
            return false
        }
        // p == q; 次の比較を試します。
    }
    // ここまで,すべての比較で "等しい" となりました。
    // それで,最後の比較結果を返します。
    return ms.less[k](p, q)
}

var changes = []Change{
    {"gri", "Go", 100},
    {"ken", "C", 150},
    {"glenda", "Go", 200},
    {"rsc", "Go", 200},
    {"r", "Go", 100},
    {"ken", "Go", 200},
    {"dmr", "C", 100},
    {"r", "C", 150},
    {"gri", "Smalltalk", 80},
}

// ExampleMultiKeys では,複数のフィールドの様々な組み合わせでソートするテクニックを紹介します。
// 1 つのフィールドを比較する Less 関数をつなげて,
// 様々なソートを実現しています。
func Example_sortMultiKeys() {
    // Change 構造体を順序づけるクロージャ。
    user := func(c1, c2 *Change) bool {
        return c1.user < c2.user
    }
    language := func(c1, c2 *Change) bool {
        return c1.language < c2.language
    }
    increasingLines := func(c1, c2 *Change) bool {
        return c1.lines < c2.lines
    }
    decreasingLines := func(c1, c2 *Change) bool {
        return c1.lines > c2.lines // 注: > は下向きに順序づけます。
    }

    // シンプルケース: user でソートします。
    OrderedBy(user).Sort(changes)
    fmt.Println("By user:", changes)

    // その他の例。
    OrderedBy(user, increasingLines).Sort(changes)
    fmt.Println("By user,<lines:", changes)

    OrderedBy(user, decreasingLines).Sort(changes)
    fmt.Println("By user,>lines:", changes)

    OrderedBy(language, increasingLines).Sort(changes)
    fmt.Println("By language,<lines:", changes)

    OrderedBy(language, increasingLines, user).Sort(changes)
    fmt.Println("By language,<lines,user:", changes)

    // Output:
    // By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
    // By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
    // By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}]
    // By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {r Go 100} {gri Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}]
    // By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]

}

例 (SortWrapper)

コード:

package sort_test

import (
    "fmt"
    "sort"
)

type Grams int

func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }

type Organ struct {
    Name   string
    Weight Grams
}

type Organs []*Organ

func (s Organs) Len() int      { return len(s) }
func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

// ByName は,自分の Less メソッドと,埋め込まれた Organs の Len と Swap メソッドとを用いて
// sort.Interface を実装します。
type ByName struct{ Organs }

func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }

// ByWeight は,自分の Less メソッドと,埋め込まれた Organs の Len と Swap メソッドとを用いて
// sort.Interface を実装します。
type ByWeight struct{ Organs }

func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }

func Example_sortWrapper() {
    s := []*Organ{
        {"brain", 1340},
        {"heart", 290},
        {"liver", 1494},
        {"pancreas", 131},
        {"prostate", 62},
        {"spleen", 162},
    }

    sort.Sort(ByWeight{s})
    fmt.Println("Organs by weight:")
    printOrgans(s)

    sort.Sort(ByName{s})
    fmt.Println("Organs by name:")
    printOrgans(s)

    // Output:
    // Organs by weight:
    // prostate (62g)
    // pancreas (131g)
    // spleen   (162g)
    // heart    (290g)
    // brain    (1340g)
    // liver    (1494g)
    // Organs by name:
    // brain    (1340g)
    // heart    (290g)
    // liver    (1494g)
    // pancreas (131g)
    // prostate (62g)
    // spleen   (162g)
}

func printOrgans(s []*Organ) {
    for _, o := range s {
        fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
    }
}

目次 ▾

パッケージファイル

search.go slice.go slice_go113.go sort.go zfuncversion.go

func Float64s

func Float64s(a []float64)

Float64s は,float64 のスライスを昇順にソートします。 (NaN は,他の値よりも小さいものとして扱います。)

コード:

s := []float64{5.2, -1.3, 0.7, -3.8, 2.6} // ソートされていない
sort.Float64s(s)
fmt.Println(s)

s = []float64{math.Inf(1), math.NaN(), math.Inf(-1), 0.0} // ソートされていない
sort.Float64s(s)
fmt.Println(s)

出力:

[-3.8 -1.3 0.7 2.6 5.2]
[NaN -Inf 0 +Inf]

func Float64sAreSorted

func Float64sAreSorted(a []float64) bool

Float64sAreSorted は, float64 のスライスが昇順にソートされているかチェックします。 (NaN は,他の値よりも小さいものとして扱います。)

コード:

s := []float64{0.7, 1.3, 2.6, 3.8, 5.2} // 昇順にソートされている
fmt.Println(sort.Float64sAreSorted(s))

s = []float64{5.2, 3.8, 2.6, 1.3, 0.7} // 降順にソートされている
fmt.Println(sort.Float64sAreSorted(s))

s = []float64{5.2, 1.3, 0.7, 3.8, 2.6} // ソートされていない
fmt.Println(sort.Float64sAreSorted(s))

出力:

true
false
false

func Ints

func Ints(a []int)

Ints は,整数のスライスを昇順にソートします。

コード:

s := []int{5, 2, 6, 3, 1, 4} // ソートされていない
sort.Ints(s)
fmt.Println(s)

出力:

[1 2 3 4 5 6]

func IntsAreSorted

func IntsAreSorted(a []int) bool

IntsAreSorted は,整数のスライスが昇順にソートされているかチェックします。

コード:

s := []int{1, 2, 3, 4, 5, 6} // 昇順にソートされている
fmt.Println(sort.IntsAreSorted(s))

s = []int{6, 5, 4, 3, 2, 1} // 降順にソートされている
fmt.Println(sort.IntsAreSorted(s))

s = []int{3, 2, 4, 1, 5} // ソートされていない
fmt.Println(sort.IntsAreSorted(s))

出力:

true
false
false

func IsSorted

func IsSorted(data Interface) bool

IsSorted は,データがソート済みかを返します。

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

Search は,二分探索を用いて f(i) が true になる [0, n) 間の最小の i を返します。 ただし,[0, n) において, f(i) == true なら f(i+1) == true である必要があります。That is, Search requires that つまり,f は [0, n) の最初のいくつか(ゼロ個のこともある)では false で, 残りはすべて true (ゼロ個のこともある) となります。 Search は最初に true となるインデックスを返します。まったく true とならない場合,n を返します。 ("見つからなかった" 場合,strings.Index のように -1 を返すのではないことに注意してください。) Search は [0, n) の範囲の i で f(i) を呼び出します。

Search の一般的な用途は,ソート済みの配列やスライス内で値 x を持つインデックス i を求める場合です。 この場合,引数 f(多くの場合,クロージャ) が,探索する値と, データ構造がどのように順序づけられているか を反映します。

例えば,スライスのデータが昇順にソートされている場合, Search(len(data), func(i int) bool { return data[i] >= 23 }) を呼び出すと,data[i] >= 23 であるような最小のインデックス i が返ります。 23 がスライスの中にあるかどうか判定したい場合, data[i] == 23 を別にチェックする必要があります。

降順でソートされたデータを探索するには, >= のかわりに <= を使います。

最後に,次のコードは,昇順にソートされている整数のスライスデータの中から 値 x を見つけます。

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
	// data[i] が x です。
} else {
	// x は data 中に存在しません。
	// x を挿入するならば,インデックス i がその場所になります。
}

ちょっとかわった例として,このプログラムは数を推測します。

func GuessingGame() {
	var s string
	fmt.Printf("0 から 100 の間の数字を一つ選んでください。\n")
	answer := sort.Search(100, func(i int) bool {
		fmt.Printf("その数字は, <= %d ですか? ", i)
		fmt.Scanf("%s", &s)
		return s != "" && s[0] == 'y'
	})
	fmt.Printf("あなたが選んだ数字は,%d です。\n", answer)
}

例 (DescendingOrder)

この例は降順でソートされているリストの中から探す方法を示しています。 方法は昇順の場合と同じですが, 条件が逆になっています。

コード:

a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6

i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
if i < len(a) && a[i] == x {
    fmt.Printf("found %d at index %d in %v\n", x, i, a)
} else {
    fmt.Printf("%d not found in %v\n", x, a)
}

出力:

found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]

func SearchFloat64s

func SearchFloat64s(a []float64, x float64) int

SearchFloat64s は,ソート済みの float64 のスライスから x を探し,Search に説明されているようにインデックスを返します。 返り値は,x が存在しないならば, x を挿入するインデックスとなります。 (返り値は len(a) の場合もあります)。 スライスは,昇順にソートされていなければなりません。

func SearchInts

func SearchInts(a []int, x int) int

SearchInts は,ソート済みの整数のスライスから x を探し,Search に説明されているようにインデックスを返します。 返り値は,x が存在しないならば, x を挿入するインデックスとなります。 (返り値は len(a) の場合もあります)。 スライスは,昇順にソートされていなければなりません。

func SearchStrings

func SearchStrings(a []string, x string) int

SearchStrings は,ソート済みの文字列のスライスから x を探し,Search に説明されているようにインデックスを返します。 返り値は,x が存在しないならば, x を挿入するインデックスとなります。 (返り値は len(a) の場合もあります)。 スライスは,昇順にソートされていなければなりません。

func Slice 1.8

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

Slice は,渡された less 関数を用いてスライスをソートします。

ソートは安定しているとは限りません。 安定したソートを行うには,SliceStable を使います。

渡された interface がスライスでない場合,パニックします。

コード:

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

func SliceIsSorted 1.8

func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool

SliceIsSorted は,スライスがソートされているかチェックします。

渡された interface がスライスでない場合,パニックします。

func SliceStable 1.8

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

SliceStable は,渡された less 関数を用いてスライスをソートします。 等しくなる要素については,もともとの順序を保ちます。

渡された interface がスライスでない場合,パニックします。

コード:

people := []struct {
    Name string
    Age  int
}{
    {"Alice", 25},
    {"Elizabeth", 75},
    {"Alice", 75},
    {"Bob", 75},
    {"Alice", 75},
    {"Bob", 25},
    {"Colin", 25},
    {"Elizabeth", 25},
}

// もとの順序を保ちつつ name でソートする
sort.SliceStable(people, func(i, j int) bool { return people[i].Name < people[j].Name })
fmt.Println("By name:", people)

// name の順序を保ちつつ age でソートする
sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println("By age,name:", people)

出力:

By name: [{Alice 25} {Alice 75} {Alice 75} {Bob 75} {Bob 25} {Colin 25} {Elizabeth 75} {Elizabeth 25}]
By age,name: [{Alice 25} {Bob 25} {Colin 25} {Elizabeth 25} {Alice 75} {Alice 75} {Bob 75} {Elizabeth 75}]

func Sort

func Sort(data Interface)

Sort は,データをソートします。 data.Len を一回呼び出し,n を決定し, data.Less と data.Swap を O(n*log(n)) 回呼び出します。ソートは安定しているとは限りません。

func Stable 1.2

func Stable(data Interface)

Stable は,等しい要素のもともとの順序を保ちつつデータをソートします。

data.Len を一回呼び出して n を決定します。 data.Less を O(n*log(n)) 回呼び出します。 data.Swap を O(n*log(n)*log(n)) 回呼び出します。

func Strings

func Strings(a []string)

Strings は,文字列のスライスを昇順にソートします。

コード:

s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
sort.Strings(s)
fmt.Println(s)

出力:

[Alpha Bravo Delta Go Gopher Grin]

func StringsAreSorted

func StringsAreSorted(a []string) bool

StringsAreSorted は,文字列のスライスが昇順にソートされているかチェックします。

type Float64Slice

Float64Slice は []float64 に Interface の昇順にソートするメソッドを追加します。 (NaN は,他の値よりも小さいものとして扱います。)

type Float64Slice []float64

func (Float64Slice) Len

func (p Float64Slice) Len() int

func (Float64Slice) Less

func (p Float64Slice) Less(i, j int) bool

func (Float64Slice) Search

func (p Float64Slice) Search(x float64) int

Search は,レシーバと x に SearchFloat64s を適用した結果を返します。

func (Float64Slice) Sort

func (p Float64Slice) Sort()

Sort は,利便性のためのメソッドです。

func (Float64Slice) Swap

func (p Float64Slice) Swap(i, j int)

type IntSlice

IntSlice は []int に Interface の昇順にソートするメソッドを追加します。

type IntSlice []int

func (IntSlice) Len

func (p IntSlice) Len() int

func (IntSlice) Less

func (p IntSlice) Less(i, j int) bool

func (IntSlice) Search

func (p IntSlice) Search(x int) int

Search は,レシーバと x に SearchInts を適用した結果を返します。

func (IntSlice) Sort

func (p IntSlice) Sort()

Sort は,利便性のためのメソッドです。

func (IntSlice) Swap

func (p IntSlice) Swap(i, j int)

type Interface

sort.Interface を満たす型 (一般的にはコレクション) は, このパッケージにある関数を使ってソートすることができます。 コレクションの要素が整数型のインデックスを使ってアクセス可能である必要があります。

type Interface interface {
    // Len は,コレクションの要素数です。
    Len() int
    // Less は,インデックス i の要素がインデックス j の要素より前に
    // 置くべきかを示します。
    Less(i, j int) bool
    // Swap は,インデックス i と j の要素を交換します。
    Swap(i, j int)
}

func Reverse 1.1

func Reverse(data Interface) Interface

Reverse は,逆順ソートを返します。

コード:

s := []int{5, 2, 6, 3, 1, 4} // ソートされていない
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)

出力:

[6 5 4 3 2 1]

type StringSlice

StringSlice は []string に Interface の昇順にソートするメソッドを追加します。

type StringSlice []string

func (StringSlice) Len

func (p StringSlice) Len() int

func (StringSlice) Less

func (p StringSlice) Less(i, j int) bool

func (StringSlice) Search

func (p StringSlice) Search(x string) int

Search は,レシーバと x に SearchStrings を適用した結果を返します。

func (StringSlice) Sort

func (p StringSlice) Sort()

Sort は,利便性のためのメソッドです。

func (StringSlice) Swap

func (p StringSlice) Swap(i, j int)