安定ソート
同値要素の順序を保持します
「安定ソート」はCoddyKit上の無料Go Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはGo Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Go Academyコースには全4レッスンが含まれています。
安定ソートとは
安定ソートでは、等しい要素の元の相対順序が維持されます。2つのレコードが同じ順序になる場合、先にあったレコードが先のままになります。
重要な理由
安定性は、あるフィールドでソートしつつ、同順位の要素について以前の順序を維持したい場合に重要です。たとえば都市でソートし、各都市内では人名のアルファベット順を保つ場合です。
sort.Slice は安定ではない
通常の sort.Slice は安定性を保証しません。等しい要素の順序が変わる可能性があります。安定性を保証するには、sort.SliceStable を使ってください。
sort.SliceStable
sort.SliceStable は sort.Slice と同じシグネチャを持ちますが、等しい要素の順序を維持します。
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{3, 1, 2, 1}
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
fmt.Println(nums)
}構造体で安定性を確認する
人物を年齢でソートします。安定ソートでは、同じ年齢の人物が入力時の順序を維持します。
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
func main() {
p := []Person{{"Ann", 30}, {"Bob", 25}, {"Cara", 30}}
sort.SliceStable(p, func(i, j int) bool {
return p[i].Age < p[j].Age
})
fmt.Println(p)
}Ann が Cara より前
前の例では、Ann と Cara はどちらも年齢が30歳です。入力では Ann が先に登場したため、安定ソートを使うと結果でも Ann が Cara より前になります。
複数回に分けたソート
安定性があると、複数回に分けてソートできます。重要度の低いキーから先にソートし、その後で最も重要なキーをソートします。安定した各ソートによって、同順位の場合はそれまでの順序が維持されます。
package main
import (
"fmt"
"sort"
)
type Rec struct {
City string
Name string
}
func main() {
r := []Rec{{"Rome", "Zoe"}, {"Oslo", "Ann"}, {"Rome", "Ann"}}
sort.SliceStable(r, func(i, j int) bool { return r[i].Name < r[j].Name })
sort.SliceStable(r, func(i, j int) bool { return r[i].City < r[j].City })
fmt.Println(r)
}sort.Stable
sort.Interface を実装する型では、安定性を得るために sort.Sort の代わりに sort.Stable を使います。
package main
import (
"fmt"
"sort"
)
type ByLen []string
func (s ByLen) Len() int { return len(s) }
func (s ByLen) Less(i, j int) bool { return len(s[i]) < len(s[j]) }
func (s ByLen) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
w := []string{"bb", "cc", "a"}
sort.Stable(ByLen(w))
fmt.Println(w)
}安定ソートのコスト
安定ソートは、不安定なソートよりもメモリや時間を少し多く使う場合があります。等しい要素の順序を維持する必要がなければ、通常の sort.Slice で問題ありません。
安定ソートを選ぶタイミング
次のような場合は安定ソートを選択してください。
- 要素に意味のある元の順序がある場合
- 異なるキーで複数回ソートする場合
- 同値の要素の順序を入れ替えたくない場合
安定ソートの確認例
同じソートキーを持つ2つの要素が、入力順にA、Bとして並んでいるとします。安定ソートを使うと、出力でも必ずAがBより前になります。
package main
import (
"fmt"
"sort"
)
func main() {
type T struct{ Key, Tag int }
ts := []T{{1, 100}, {1, 200}, {0, 300}}
sort.SliceStable(ts, func(i, j int) bool { return ts[i].Key < ts[j].Key })
fmt.Println(ts)
}確認問題
sort.SliceStableを使ってレコードを都市名でソートします。同じ都市のレコードが2つある場合、何が保証されますか。
まとめ
安定ソートは、同値の要素の順序を維持します。
- スライスには
sort.SliceStableを使用します sort.Interface型にはsort.Stableを使用します- 異なるキーによる複数回のソートが可能になります
よくある質問
「安定ソート」レッスンは無料ですか？
はい。「安定ソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Go Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Go Academyコースには全4レッスンが含まれています。
「安定ソート」で何を学びますか？
同値要素の順序を保持します ブラウザで直接実行するハンズオンコードでGo Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Go Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのGo Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「安定ソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このGo Academyレッスンでコードを書いて実行できますか？
はい。すべてのGo Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。