Help us understand the problem. What is going on with this article?

GoのSliceをSortする(sort.Sliceとsort.SliceStable)

More than 1 year has passed since last update.

GoのSliceをSortする(sort.Sliceとsort.SliceStable)

sort.Sliceとsort.SliceStableを使用してGoのSliceをSortしてみる。

本記事のコード全体は以下。
https://play.golang.org/p/Lnj8kAwWxyy

安定ソート(stable sort)とは

まずsortは安定ソートかどうかで挙動が異なる

安定ソート(stable sort)については以下がわかりやすいので引用させていただいた。

安定ソート(あんていソート、stable sort)とは、ソート(並び替え)のアルゴリズムのうち、同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。
たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。

引用元 : 安定ソート - Wikipedia

Goのsort packageのSliceとSliceStable

Goのsort packageには、安定ソートを保証しないSlice関数と安定ソートを保証するSliceStableが存在する。

それぞれ以下で実装とその結果を記す

sort.Slice

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

安定ソートを保証しない。
第二引数で与えたless関数を使用して、第一引数で与えたSliceをソートする。
安定ソートを行うには、SliceStableを使用する。

実装

        people := []Person{
            {Name: "V", Age: 3},
            {Name: "K", Age: 3},
            {Name: "Y", Age: 3},
            {Name: "A", Age: 4},
            {Name: "E", Age: 3},
            {Name: "D", Age: 1},
            {Name: "C", Age: 3},
            {Name: "X", Age: 2},
            {Name: "B", Age: 3},
        }

        sort.Slice(people, func(i, j int) bool { return people[i].Name < people[j].Name })
        fmt.Printf("NameでSort(Not-Stable):%+v\n", people)

        sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
        fmt.Printf("AgeでSort(Not-Stable):%+v\n", people)

実行結果

NameでSort(Not-Stable):[{Name:A Age:4} {Name:B Age:3} {Name:C Age:3} {Name:D Age:1} {Name:E Age:3} {Name:K Age:3} {Name:V Age:3} {Name:X Age:2} {Name:Y Age:3}]
AgeでSort(Not-Stable):[{Name:D Age:1} {Name:X Age:2} {Name:V Age:3} {Name:C Age:3} {Name:E Age:3} {Name:K Age:3} {Name:B Age:3} {Name:Y Age:3} {Name:A Age:4}]

sort.SliceStable

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

安定ソートを行う

people2 := []Person{
        {Name: "V", Age: 3},
        {Name: "K", Age: 3},
        {Name: "Y", Age: 3},
        {Name: "A", Age: 4},
        {Name: "E", Age: 3},
        {Name: "D", Age: 1},
        {Name: "C", Age: 3},
        {Name: "X", Age: 2},
        {Name: "B", Age: 3},
    }

    sort.SliceStable(people2, func(i, j int) bool { return people2[i].Name < people2[j].Name })
    fmt.Printf("NameでSort(Stable):%+v\n", people2)

    sort.SliceStable(people2, func(i, j int) bool { return people2[i].Age < people2[j].Age })
    fmt.Printf("AgeでSort:%+v\n", people2)
}

実行結果

NameでSort(Stable):[{Name:A Age:4} {Name:B Age:3} {Name:C Age:3} {Name:D Age:1} {Name:E Age:3} {Name:K Age:3} {Name:V Age:3} {Name:X Age:2} {Name:Y Age:3}]
AgeでSort:[{Name:D Age:1} {Name:X Age:2} {Name:B Age:3} {Name:C Age:3} {Name:E Age:3} {Name:K Age:3} {Name:V Age:3} {Name:Y Age:3} {Name:A Age:4}]

ソート前の順序が、ソート後も保存されている。
Nameで、整列済みのPersonデータを、AGEの順で安定ソートを用いて並べ替えると、ソート後のデータは、同じAGEのPersonはName順で並んでいる。

参考にさせていただいた記事

sort - The Go Programming Language
安定ソート - Wikipedia

Sekky0905
最近GoとGCPに戻ってきました。 以前は、GAE/Go、AWS、TypeScript、Angular、Vueをやっていました。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away