import "sort"

sortパッケージは、配列やユーザ定義のコレクションをソートするためのプリミティブを提供します。

パッケージファイル

search.go sort.go

FloatsAreSorted関数

func FloatsAreSorted(a []float) bool

FloatsAreSortedは、floatの配列が昇順に格納されているか調べます。

IntsAreSorted関数

func IntsAreSorted(a []int) bool

IntsAreSortedは、intの配列が昇順に格納されているか調べます。

IsSorted関数

func IsSorted(data Interface) bool

func Search(n int, f func(int) bool) int

Searchは、バイナリサーチを利用して、[0, n)内のf(i)が真となる最小インデックスを探して返します。このとき[0, n)範囲内で、f(i) == trueのときは必ずf(i+1) == trueも成り立つとみなします。つまりSearchは、fが入力範囲[0, n)の前半(0個でもよい)でfalseを返し、それ以降(0個でもよい)ではtrueを返すことを期待します。Searchは、最初にtrueとなるインデックスを返します。

Searchは一般的に、ソート済みで、配列やスライスといったインデックス指定可能なデータ構造に格納されている値xのインデックスiを検索するために使用します。この場合、引数f(一般的にクロージャ)は、探すべき値と、このデータ構造がどのようにインデックスされていて、どのような順番であるかを知っている必要があります。

例えば、昇順にデータが格納されたスライスで、Search(len(data), func(i int) bool { return data[i] >= 23 })を呼び出すと、data[i] >= 23となる最小のインデックスが返されます。呼び出し元が、23がスライス内にあるかどうか知りたいときは、別途data[i] == 23であるか調べなければなりません。

検索対象のデータが降順に格納されているときは、>=演算子の代わりに<=を使います。

上の例の完成版として、この下のコードは、昇順にデータが格納された整数スライス内で値xを探そうと試みています。

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
	// xは、data[i]に存在する
} else {
	// xはdata内に存在しないが、
	// iは、xを挿入可能なインデックスである
}

もっとおもしろい例として、このプログラムは、数値を推測します:

func GuessingGame() {
	var s string
	fmt.Printf("Pick an integer from 0 to 100.\n")
	answer := sort.Search(100, func(i int) bool {
		fmt.Printf("Is your number <= %d? ", i)
		fmt.Scanf("%s", &s)
		return s != "" && s[0] == 'y'
	})
	fmt.Printf("Your number is %d.\n", answer)
}

SearchFloats関数

func SearchFloats(a []float, x float) int

SearchFloatsは、ソート済みfloatのスライスからxを検索し、Searchで規定されているインデックスを返します。配列は昇順でソートされている必要があります。

SearchInts関数

func SearchInts(a []int, x int) int

SearchIntsは、ソート済みintのスライスからxを検索し、Searchで規定されているインデックスを返します。配列は昇順でソートされている必要があります。

SearchStrings関数

func SearchStrings(a []string, x string) int

SearchStringsは、ソート済みstringのスライスからxを検索し、Searchで規定されているインデックスを返します。配列は昇順でソートされている必要があります。

Sort関数

func Sort(data Interface)

SortFloats関数

func SortFloats(a []float)

SortFloatsは、floatの配列を昇順にソートします。

SortInts関数

func SortInts(a []int)

SortIntsは、intの配列を昇順にソートします。

SortStrings関数

func SortStrings(a []string)

SortStringsは、stringの配列を昇順にソートします。

StringsAreSorted関数

func StringsAreSorted(a []string) bool

StringsAreSortedは、stringの配列が昇順に格納されているか調べます。

FloatArray型

FloatArrayは、昇順ソートを行うInterfaceのメソッドを[]floatに結びつけます。

type FloatArray []float

(FloatArray) Len関数

func (p FloatArray) Len() int

(FloatArray) Less関数

func (p FloatArray) Less(i, j int) bool

(FloatArray) Search関数

func (p FloatArray) Search(x float) int

Searchは、レシーバとxをSearchFloatsに適用した結果を返します。

(FloatArray) Sort関数

func (p FloatArray) Sort()

Sortは、コンビニエンスメソッドです。

(FloatArray) Swap関数

func (p FloatArray) Swap(i, j int)

IntArray型

IntArray は、昇順ソートを行うInterfaceのメソッドを[]intに結びつけます。

type IntArray []int

(IntArray) Len関数

func (p IntArray) Len() int

(IntArray) Less関数

func (p IntArray) Less(i, j int) bool

(IntArray) Search関数

func (p IntArray) Search(x int) int

Searchは、レシーバとxをSearchIntsに適用した結果を返します。

(IntArray) Sort関数

func (p IntArray) Sort()

Sortは、コンビニエンスメソッドです。

(IntArray) Swap関数

func (p IntArray) Swap(i, j int)

Interface型

sort.Interfaceを満たしている型(通常はコレクション)は、このパッケージ内のルーチンを使ってソートできます。メソッドに必要なのは、コレクションの要素が整数値のインデックスを使って順にアクセスできることです。

type Interface interface {
    // Lenは、コレクション内の要素数。
    Len() int
    // Lessは、インデックスiで示される要素がインデックスjの前に
    // 並び替えるべきかを返します。
    Less(i, j int) bool
    // Swapは、インデックスi,jの要素を入れ替える。
    Swap(i, j int)
}

StringArray型

StringArrayは、昇順ソートを行うInterfaceのメソッドを[]stringに結びつけます。

type StringArray []string

(StringArray) Len関数

func (p StringArray) Len() int

(StringArray) Less関数

func (p StringArray) Less(i, j int) bool

(StringArray) Search関数

func (p StringArray) Search(x string) int

Searchは、レシーバとxをSearchStringsに適用した結果を返します。

(StringArray) Sort関数

func (p StringArray) Sort()

Sortは、コンビニエンスメソッドです。

(StringArray) Swap関数

func (p StringArray) Swap(i, j int)