実行できるGoドキュメント: ソート

Q: Goでスライスをソートするには？

数値や文字列なら slices.Sort(s)（Go 1.21）を呼びます。その場で昇順にソートします。それ以外の型や別の順序には slices.SortFunc(s, func(a, b T) int { ... }) を使います。関数は a が先なら負の数、b が先なら正の数、等しければ0を返します。

Q: Goでスライスを降順にソートするには？

比較の引数を入れ替えます：slices.SortFunc(s, func(a, b int) int { return cmp.Compare(b, a) })。または昇順にソートしてから slices.Reverse(s) を呼びます。

Q: Goで構造体のスライスを複数のフィールドでソートするには？

最初のフィールドを比較し、それが等しいときだけ次のフィールドに進みます。cmp.Or（Go 1.22）がまさにそれをします：return cmp.Or(cmp.Compare(a.Dept, b.Dept), cmp.Compare(b.Salary, a.Salary), strings.Compare(a.Name, b.Name)) は最初の0でない結果を返します。

Q: sort.Sliceとslices.SortFuncの違いは何ですか？

sort.Slice(s, func(i, j int) bool) は古いAPIで、インデックスに対するless関数を受け取り、要素の入れ替えにリフレクションを使います。slices.SortFunc(s, func(a, b T) int) はジェネリックで型チェックされ、要素を直接受け取り、より高速です。新しいコードでは slices パッケージを使いましょう。sort.Slice はGo 1.21より前に書かれたコードでは今でもよく見かけます。

組み込み型をソートする

slices.Sort は、要素の型が順序付け可能（整数、浮動小数点数、文字列）なスライスならどれでもソートします。その場でソートし、何も返しません。

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

出力：

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

文字列はバイトでソートされるので、ASCIIの大文字はすべて小文字より前に来ます。名前の並びとして利用者が期待するものとは、たいてい違います。次の節でこれを直します。

slices パッケージはGo 1.21で入りました。その Sort はpattern-defeating quicksortで、O(n log n)、その場でのソート、安定ではありません。

SortFuncで独自の順序にする

slices.SortFunc は比較関数 func(a, b T) int を受け取ります。a を先にすべきなら負の数、b を先にすべきなら正の数、等しければ0を返します。cmp.Compare ヘルパーは、順序付け可能な型に対してちょうどそれを返します。

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

比較の中の strings.ToLower は、入力に大文字が含まれるたびに新しい文字列を確保し、比較はおよそ n log n 回実行されます。大きなスライスでは、小文字にしたキーを一度だけ計算しておきます。他の言語の名前（アクセント、ロケールのルール）には、標準ライブラリの外にある golang.org/x/text/collate を使います。

比較関数は一貫していなければなりません。a が b より前だと言うなら、b は a より後だと言う必要があります。これを破る関数（たとえば2つの値が違えば常に -1 を返す）は、エラーもなく間違った順序のスライスを作ります。整数の引き算（return a - b）はすっきり見えますが、大きな値でオーバーフローします。cmp.Compare を使います。

構造体をソートする

比較関数は要素を受け取るので、構造体をフィールドでソートするのも同じ呼び出しです。

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

SortFunc は安定ではないので、ここでは給与が等しい社員がどの順序で出てきても構いません。順序を保証したいなら、さらにフィールドを使って同順位を解消するか、安定ソートを使います。

複数のフィールドでソートする

最も重要なフィールドを先に比較し、同順位のときだけ次に進みます。cmp.Or（Go 1.22）は最初の0でない引数を返すので、これが1行になります。

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

出力：

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

比較はただの引数なので、最初の比較で決まってもすべての比較が評価されます。フィールドの比較ならほとんどコストはかかりません。同順位の解消が重いときは、if c := ...; c != 0 { return c } の連鎖を手で書きます。

安定ソート

安定ソートは、等しいと比較される要素を元の順序のまま保ちます。入力にすでに意味のある順序がある場合、たとえば時刻順のレコードをユーザーごとにまとめる場合に重要になります。

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

これは [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}] と表示します。ユーザーごとに、元の順番が保たれています。安定ソートは処理が多いので、等しい要素の順序が重要なときだけ使います。

マップをソートする

マップに順序はありません。マップをキーでソートして表示するには、キーをソートします：slices.Sorted(maps.Keys(m))（Go 1.23）。値でソートするには、値を参照する比較でキーをソートします。

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

単語による同順位の解消が重要です。これがないと、chan と slice（どちらも7）は実行のたびに違う順序で表示されます。キーがランダムな順序でマップから出てくるからです。詳しくはマップのページを参照してください。

sortパッケージ：sort.Sliceとその仲間

Go 1.21より前は、ソートは sort パッケージを通して行っていました。既存のコードの多くで見かけます。

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

知っておきたい違いは次のとおりです。

	`sort.Slice`	`slices.SortFunc`
関数が受け取るもの	インデックス `i, j`	要素 `a, b`
戻り値	`bool`（iがjより小さいか）	`int`（負、0、正）
型安全性	`any` を受け取り、リフレクションを使う	ジェネリックで、コンパイル時にチェック
速度	遅い	速い

sort.Slice のよくあるバグは、less関数が位置でインデックスを使うため、ソートしているのとは別のスライスを捕捉してしまうことです。SortFunc は要素を渡してくれるので、このバグは起こりえません。

sort.Interface 型（Len、Less、Swap）は最も古い形です。一緒に動かさなければならない2つの並列なスライスのように、1つのスライスではないデータをソートするには今でもこれを使います。Go 1.22以降、sort.Ints、sort.Strings、sort.Float64s は単に slices.Sort を呼んでいます。

よくある間違い

Sort がソートしたスライスを返すと思う。 その場でソートし、何も返しません。新しいソート済みのスライスがほしいなら slices.Sorted(slices.Values(s)) を使うか、先に slices.Clone します。
等しい要素が順序を保つと思い込む。 それを保証するのは Stable 版だけです。
引き算で比較する。 a - b はオーバーフローします。cmp.Compare を使います。
NaNを含む浮動小数点数をソートする。 cmp.Compare はNaNを他のどの値よりも前に並べるので、ソートの一貫性が保たれます。手書きの a < b の比較ではそうなりません。

よくある質問

Goでスライスをソートするには？

数値や文字列なら slices.Sort(s)（Go 1.21）を呼びます。その場で昇順にソートします。それ以外の型や別の順序には slices.SortFunc(s, func(a, b T) int { ... }) を使います。関数は a が先なら負の数、b が先なら正の数、等しければ0を返します。

Goでスライスを降順にソートするには？

比較の引数を入れ替えます：slices.SortFunc(s, func(a, b int) int { return cmp.Compare(b, a) })。または昇順にソートしてから slices.Reverse(s) を呼びます。

Goで構造体のスライスを複数のフィールドでソートするには？

最初のフィールドを比較し、それが等しいときだけ次のフィールドに進みます。cmp.Or（Go 1.22）がまさにそれをします：return cmp.Or(cmp.Compare(a.Dept, b.Dept), cmp.Compare(b.Salary, a.Salary), strings.Compare(a.Name, b.Name)) は最初の0でない結果を返します。

sort.Sliceとslices.SortFuncの違いは何ですか？

sort.Slice(s, func(i, j int) bool) は古いAPIで、インデックスに対するless関数を受け取り、要素の入れ替えにリフレクションを使います。slices.SortFunc(s, func(a, b T) int) はジェネリックで型チェックされ、要素を直接受け取り、より高速です。新しいコードでは slices パッケージを使いましょう。sort.Slice はGo 1.21より前に書かれたコードでは今でもよく見かけます。