[Go] sort.Sliceで文字列を辞書順にソートする

はじめに

最近、Go言語で文字列を辞書順にソートしたい場面があり、少し調べてみるとGoの標準パッケージであるsortパッケージのSlice関数というのを使えば出来そうだということが分かりました。
そこで公式ドキュメントのsort.Sliceの使い方の説明を見たところ、こんな処理の書き方初めて見た、Slice関数の中でどのように処理されているのかいまいちイメージがつかないという部分があったので詳しく調べてみました。
この記事では、初めに結論としてsort.Sliceで文字列を辞書順にソートする方法を説明し、その後sort.Sliceは中でどのように処理を行なっているのかを確かめてみます。

対象読者

• Go言語を使用して文字列を辞書順にソートしたい人
• sort.Sliceの中でどのように処理されているのかを知りたい人

文字列を辞書順にソートする方法

Goの標準パッケージであるsortパッケージのSlice関数を使うと、文字列を辞書順にソートすることができます。

package main

import (
	"fmt"
	"sort"
)

func main() {
	names := []string{"Gopher", "Alice", "Vera", "Bob"}
		
	sort.Slice(names, func(i, j int) bool { return names[i] < names[j] })
	fmt.Println(names)
}

出力結果

[Alice Bob Gopher Vera]

sort.Sliceとは？

これはGoのsortパッケージにある関数で任意のスライスを、指定したルールで並び替える便利なやつです。

// 第一引数にソートしたいスライス、第二引数にどんなルールでソートするかの比較関数を渡す
sort.Slice(slice, lessFunc)
// 例
sort.Slice(names, func(i, j int) bool { return names[i] < names[j] })

上記の例の場合だと、namesスライスを対象にfunc(i, j int) boolという比較関数を渡して、names[i]とnames[j]を比べて並び順が正しいかを判定しています。

比較関数の説明

• iとjは、namesスライス中の2つのインデックス
• names[i] < names[j]は、この比較がtrueなら「i番目はj番目より前にあるべき」、falseなら「i番目とj番目の値の順番を入れ替える」というのを必要に応じて行なっています

sort.Sliceは中でどんな処理を行なっているのか

初め比較関数のコードを見た時こう思いました。
なんでこれで比較ができるのか？
iとjには具体的にどんな値が入っているのだろう？
結論から言うと
iとjは、sort.Sliceの中の仕組みで自動的に渡されている引数です。
つまり、iとjには自動的にスライスのインデックス番号が入り、比較する必要があればsort.Slice内部のソートの処理で何度も比較関数が呼ばれ、文字列をソートします。

処理の過程をログを出力して見てみる

それでは実際にiやjにはどんな値が入っていて、どんな風に値がソートされているのかをログを仕込んで確認してみます。

package main

import (
    "fmt"
    "sort"
)

func main() {
	names := []string{"Gopher", "Alice", "Vera", "Bob"}
		
	sort.Slice(names, func(i, j int) bool {
	    fmt.Println(names)
	    fmt.Printf("Comparing: names[%d] = %v vs names[%d] = %v\n", i, names[i], j, names[j])
	    return names[i] < names[j] 
	})
	
	fmt.Printf("result: %v", names)
}

出力結果

[Gopher Alice Vera Bob]
Comparing: names[1] = Alice vs names[0] = Gopher
[Alice Gopher Vera Bob]
Comparing: names[2] = Vera vs names[1] = Gopher
[Alice Gopher Vera Bob]
Comparing: names[3] = Bob vs names[2] = Vera
[Alice Gopher Bob Vera]
Comparing: names[2] = Bob vs names[1] = Gopher
[Alice Bob Gopher Vera]
Comparing: names[1] = Bob vs names[0] = Alice
result: [Alice Bob Gopher Vera]

出力結果を見ると、まず1番目のAliceと0番目のGopherを比較しています。Alice < Gopherなので順番を入れ替えます。次に2番目のVeraと1番目のGopherを比較しています。Gopher < Veraなので入れ替えは発生しません。というように、順番の入れ替えが発生しなくなるまで比較関数が何度も呼び出され、要素の入れ替え処理を行います。
この結果を見ると、どうやらスライスの前の方から比較していき、要素の入れ替えが発生したら、入れ替えた要素の一つ前の要素と比較というのを繰り返しているように見えます。

sort.Sliceの他にオススメされている方法

一方でsort.Sliceの公式ドキュメントにはこのようなことが書いてありました。

Note: in many situations, the newer slices.SortFunc function is more ergonomic and runs faster.

日本語訳すると

多くの場合、新しいslice.SortFunc関数の方がより人間工学的で高速に実行されます。

Go1.21以降で追加されたslices.SortFuncという関数もあるみたいです。
ここに書くと長くなってしまうため、こちらについては[Go] slices.SortFuncで文字列を辞書順にソートするで解説したいと思います。

まとめ

本記事では、Go言語で文字列を辞書順にソートする方法を紹介しました。
Goの標準パッケージであるsort.Sliceを使えば、任意のスライスを指定したルールで並び替えることができます。
加えて、sort.Sliceの中で処理がどのように行われているのかを実際にログを出力して確認してみました。
ログを出力してみると、実際にどんな風に処理されているのかなということを実感できて理解が深まりました。