◀️
【Go】Goで学ぶ安定ソートと不安定ソート
はじめに
自己学習中に「安定ソート」「不安定ソート」という用語に出会い、その違いや具体的な使い方を知りたくなりました。
この記事では、それぞれの意味をわかりやすく整理し、Goでの実装方法を紹介します！
📝安定ソートと不安定ソート
🔹安定ソート
- 同じ値の要素の、元の順序を保持するソートアルゴリズム
- 例えば、生徒の名前順で並び替えられているデータを成績順でソートする際に、元の名前順を保持したまま成績順で並び替えることができる
🔸不安定ソート
- 同じ値の要素の元の順序を保持しない可能性があるソートアルゴリズム
- 例えば、生徒の名前順で並び替えられているデータを成績順でソートする際に、元の名前順を保持しない状態で成績順で並び替えることになる
🛠️Goでの実装方法
1. 📁sortパッケージの活用
| 関数名 | 安定性 | 概要 |
|---|---|---|
SliceStable |
🔹安定 | 順序を保ったまま並び替え |
Slice |
🔸不安定 | 順序を保たない可能性あり |
どちらも第一引数にはソートしたいスライスを、第二引数には比較関数をおく
比較関数内で要素を比較し、trueを返すとi番目の要素をj番目の要素より前に配置する
🔹安定ソートの場合
main.go
package main
import (
"fmt"
"sort"
)
type Student struct {
StudentID int
Name string
Score int
}
func main() {
// 学生番号順に並び替え済み
data := []Student{
{StudentID: 1, Name: "Aさん", Score: 200},
{StudentID: 2, Name: "Bさん", Score: 100},
{StudentID: 3, Name: "Cさん", Score: 100},
{StudentID: 4, Name: "Dさん", Score: 300},
{StudentID: 5, Name: "Eさん", Score: 200},
{StudentID: 6, Name: "Fさん", Score: 300},
}
sort.SliceStable(data, func(i, j int) bool { return data[i].Score < data[j].Score })
fmt.Println("成績順:", data)
}
🔸不安定ソートの場合
main.go
package main
import (
"fmt"
"sort"
)
type Student struct {
StudentID int
Name string
Score int
}
func main() {
// 学生番号順に並び替え済み
data := []Student{
{StudentID: 1, Name: "Aさん", Score: 200},
{StudentID: 2, Name: "Bさん", Score: 100},
{StudentID: 3, Name: "Cさん", Score: 100},
{StudentID: 4, Name: "Dさん", Score: 300},
{StudentID: 5, Name: "Eさん", Score: 200},
{StudentID: 6, Name: "Fさん", Score: 300},
}
sort.Slice(data, func(i, j int) bool { return data[i].Score < data[j].Score })
fmt.Println("成績順:", data)
}
出力例
ターミナル
// 安定ソート
成績順: [{2 Bさん 100} {3 Cさん 100} {1 Aさん 200} {5 Eさん 200} {4 Dさん 300} {6 Fさん 300}]
// 不安定ソート
成績順: [{2 Bさん 100} {3 Cさん 100} {1 Aさん 200} {5 Eさん 200} {4 Dさん 300} {6 Fさん 300}]
// 今回はたまたまどちらも同じ順序になっていたが、不安定ソートは元の並び順を保証しない
2. 📁slicesパッケージの活用
| 関数名 | 安定性 | 概要 |
|---|---|---|
SortStableFunc |
🔹安定 | 順序を保ったまま並び替え |
SortFunc |
🔸不安定 | 順序を保たない可能性あり |
どちらも第一引数にはソートしたいスライスを、第二引数には比較関数をおく
比較関数内で要素を比較し、-1を返すとaをbより先に配置(0を返すと順序の変更はなく、1の場合はbをaより先に配置)
🔹安定ソートの場合
main.go
package main
import (
"cmp"
"fmt"
"slices"
)
type Student struct {
StudentID int
Name string
Score int
}
func main() {
// 学生番号順に並び替え済み
data := []Student{
{StudentID: 1, Name: "Aさん", Score: 200},
{StudentID: 2, Name: "Bさん", Score: 100},
{StudentID: 3, Name: "Cさん", Score: 100},
{StudentID: 4, Name: "Dさん", Score: 300},
{StudentID: 5, Name: "Eさん", Score: 200},
{StudentID: 6, Name: "Fさん", Score: 300},
}
slices.SortStableFunc(data, func(a, b Student) int {
return cmp.Compare(a.Score, b.Score)
})
fmt.Println("成績順:", data)
}
🔸不安定ソートの場合
main.go
package main
import (
"cmp"
"fmt"
"slices"
)
type Student struct {
StudentID int
Name string
Score int
}
func main() {
// 学生番号順に並び替え済み
data := []Student{
{StudentID: 1, Name: "Aさん", Score: 200},
{StudentID: 2, Name: "Bさん", Score: 100},
{StudentID: 3, Name: "Cさん", Score: 100},
{StudentID: 4, Name: "Dさん", Score: 300},
{StudentID: 5, Name: "Eさん", Score: 200},
{StudentID: 6, Name: "Fさん", Score: 300},
}
slices.SortFunc(data, func(a, b Student) int {
return cmp.Compare(a.Score, b.Score)
})
fmt.Println("成績順:", data)
}
出力例
ターミナル
// 安定ソート
成績順: [{2 Bさん 100} {3 Cさん 100} {1 Aさん 200} {5 Eさん 200} {4 Dさん 300} {6 Fさん 300}]
// 不安定ソート
成績順: [{2 Bさん 100} {3 Cさん 100} {1 Aさん 200} {5 Eさん 200} {4 Dさん 300} {6 Fさん 300}]
// 今回はたまたまどちらも同じ順序になっていたが、不安定ソートは元の並び順を保証しない
💬補足
例えば、sort.SliceStable のコメントにはこうあります。
// In many situations, the newer slices.SortStableFunc function is more
// ergonomic and runs faster.
DeepL翻訳すると
// 注意: 多くの場合、より新しい[slice.SortFunc]関数の方が
// 人間工学的に優れており、高速に実行される。
ソートする場合、sortパッケージよりもslicesパッケージを使った方が高速に処理できるので、slicesパッケージを使うと良いかと思います。
✅まとめ
- 安定ソートとは、同じ値の順序が変わらないソートのこと（不安定ソートはそれを保証しない）
- 順序が重要なデータ（例：ユーザーの入力順）では安定ソートが推奨
-
sortパッケージでもslicesパッケージでも実装可能だが、slicesパッケージの方がジェネリクスでより柔軟かつ高速
✏️参考
Discussion