sort

package
v1.21.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 6, 2023 License: MIT Imports: 0 Imported by: 0

Documentation

Overview

Package sort はスライスやユーザー定義のコレクションをソートするための基本機能を提供します。

Example 
people := []Person{
	{"Bob", 31},
	{"John", 42},
	{"Michael", 17},
	{"Jenny", 26},
}

fmt.Println(people)

// スライスをソートする方法は2つあります。最初に、ByAgeなどのスライス型のためのメソッドセットを定義し、sort.Sortを呼び出すことができます。この最初の例では、その技術を使用しています。
sort.Sort(ByAge(people))
fmt.Println(people)

// もう一つの方法は、カスタムのLess関数を使用してsort.Sliceを利用することです。
// これはクロージャとして提供することができます。この場合、メソッドは必要ありません。
// (存在する場合は無視されます。) ここでは逆順で再ソートします：クロージャとByAge.Lessを比較します。
sort.Slice(people, func(i, j int) bool {
	return people[i].Age > people[j].Age
})
fmt.Println(people)

Output:
[Bob: 31 John: 42 Michael: 17 Jenny: 26]
[Michael: 17 Jenny: 26 Bob: 31 John: 42]
[John: 42 Bob: 31 Jenny: 26 Michael: 17]
Example (SortKeys)

ExampleSortKeysは、プログラム可能なソート基準を使用して構造体タイプをソートするためのテクニックを示しています。 

// プラネット構造体を順序付けるクロージャー。
name := func(p1, p2 *Planet) bool {
	return p1.name < p2.name
}
mass := func(p1, p2 *Planet) bool {
	return p1.mass < p2.mass
}
distance := func(p1, p2 *Planet) bool {
	return p1.distance < p2.distance
}
decreasingDistance := func(p1, p2 *Planet) bool {
	return distance(p2, p1)
}

// 各種基準で惑星をソートします。
By(name).Sort(planets)
fmt.Println("By name:", planets)

By(mass).Sort(planets)
fmt.Println("By mass:", planets)

By(distance).Sort(planets)
fmt.Println("By distance:", planets)

By(decreasingDistance).Sort(planets)
fmt.Println("By decreasing distance:", planets)

Output:
By name: [{Earth 1 1} {Mars 0.107 1.5} {Mercury 0.055 0.4} {Venus 0.815 0.7}]
By mass: [{Mercury 0.055 0.4} {Mars 0.107 1.5} {Venus 0.815 0.7} {Earth 1 1}]
By distance: [{Mercury 0.055 0.4} {Venus 0.815 0.7} {Earth 1 1} {Mars 0.107 1.5}]
By decreasing distance: [{Mars 0.107 1.5} {Earth 1 1} {Venus 0.815 0.7} {Mercury 0.055 0.4}]
Example (SortMultiKeys)

ExampleMultiKeysは、比較に異なる複数のフィールドのセットを使用してstructタイプをソートするためのテクニックを示しています。各フィールドを比較する「Less」関数を連鎖させます。 

// Change構造体を順序付けるクロージャー。
user := func(c1, c2 *Change) bool {
	return c1.user < c2.user
}
language := func(c1, c2 *Change) bool {
	return c1.language < c2.language
}
increasingLines := func(c1, c2 *Change) bool {
	return c1.lines < c2.lines
}
decreasingLines := func(c1, c2 *Change) bool {
	return c1.lines > c2.lines // 注意：> は下方向に並べ替えます。
}

// 簡単な使い方: ユーザーでソートする。
OrderedBy(user).Sort(changes)
fmt.Println("By user:", changes)

// もっと多くの例。
OrderedBy(user, increasingLines).Sort(changes)
fmt.Println("By user,<lines:", changes)

OrderedBy(user, decreasingLines).Sort(changes)
fmt.Println("By user,>lines:", changes)

OrderedBy(language, increasingLines).Sort(changes)
fmt.Println("By language,<lines:", changes)

OrderedBy(language, increasingLines, user).Sort(changes)
fmt.Println("By language,<lines,user:", changes)

Output:
By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}]
By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]
By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]
Example (SortWrapper) 
s := []*Organ{
	{"brain", 1340},
	{"heart", 290},
	{"liver", 1494},
	{"pancreas", 131},
	{"prostate", 62},
	{"spleen", 162},
}

sort.Sort(ByWeight{s})
fmt.Println("Organs by weight:")
printOrgans(s)

sort.Sort(ByName{s})
fmt.Println("Organs by name:")
printOrgans(s)

Output:
Organs by weight:
prostate (62g)
pancreas (131g)
spleen   (162g)
heart    (290g)
brain    (1340g)
liver    (1494g)
Organs by name:
brain    (1340g)
heart    (290g)
liver    (1494g)
pancreas (131g)
prostate (62g)
spleen   (162g)

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Find added in v1.19.0 

func Find(n int, cmp func(int) int) (i int, found bool)

Find uses binary search to find and return the smallest index i in [0, n) at which cmp(i) <= 0. If there is no such index i, Find returns i = n. The found result is true if i < n and cmp(i) == 0. Find calls cmp(i) only for i in the range [0, n).

To permit binary search, Find requires that cmp(i) > 0 for a leading prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for the final suffix of the range. (Each subrange could be empty.) The usual way to establish this condition is to interpret cmp(i) as a comparison of a desired target value t against entry i in an underlying indexed data structure x, returning <0, 0, and >0 when t < x[i], t == x[i], and t > x[i], respectively.

For example, to look for a particular string in a sorted, random-access list of strings: 

i, found := sort.Find(x.Len(), func(i int) int {
    return strings.Compare(target, x.At(i))
})
if found {
    fmt.Printf("found %s at entry %d\n", target, i)
} else {
    fmt.Printf("%s not found, would insert at %d", target, i)
}

func Float64s 

func Float64s(x []float64)

Float64sはfloat64のスライスを昇順でソートします。 NaN(非数)の値は他の値よりも優先的に並べられます。

注意：より速く実行される新しいslices.Sort関数を使用することを検討してください。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/math"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []float64{5.2, -1.3, 0.7, -3.8, 2.6} // ソートされていない
	sort.Float64s(s)
	fmt.Println(s)

	s = []float64{math.Inf(1), math.NaN(), math.Inf(-1), 0.0} // 未整列
	sort.Float64s(s)
	fmt.Println(s)

}

Output:
[-3.8 -1.3 0.7 2.6 5.2]
[NaN -Inf 0 +Inf]

func Float64sAreSorted 

func Float64sAreSorted(x []float64) bool

Float64sAreSortedは、スライスxが昇順に並んでいるか、NaN（非数値）の値が他の値の前にあるかどうかを報告します。

注意: より新しいslices.IsSorted関数を使用することを検討してください。これはより高速に実行されます。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []float64{0.7, 1.3, 2.6, 3.8, 5.2} // 昇順でソートされています
	fmt.Println(sort.Float64sAreSorted(s))

	s = []float64{5.2, 3.8, 2.6, 1.3, 0.7} // 降順でソート済み
	fmt.Println(sort.Float64sAreSorted(s))

	s = []float64{5.2, 1.3, 0.7, 3.8, 2.6} // 未整列
	fmt.Println(sort.Float64sAreSorted(s))

}

Output:
true
false
false

func Ints 

func Ints(x []int)

Intsはintのスライスを昇順にソートします。

注意: より高速に動作する新しいslices.Sort関数を使用することを検討してください。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4} // ソートされていない
	sort.Ints(s)
	fmt.Println(s)
}

Output:
[1 2 3 4 5 6]

func IntsAreSorted 

func IntsAreSorted(x []int) bool

IntsAreSortedは、スライスxが昇順にソートされているかどうかを報告します。

注意: より速く実行する新しいslices.IsSorted関数を使用することを考慮してください。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []int{1, 2, 3, 4, 5, 6} // 昇順でソートされています
	fmt.Println(sort.IntsAreSorted(s))

	s = []int{6, 5, 4, 3, 2, 1} // 降順で並べ替え済み
	fmt.Println(sort.IntsAreSorted(s))

	s = []int{3, 2, 4, 1, 5} // 未ソート
	fmt.Println(sort.IntsAreSorted(s))

}

Output:
true
false
false

func IsSorted 

func IsSorted(data Interface) bool

IsSortedはデータがソートされているかどうかを報告します。

注意：多くの場合、新しいslices.IsSortedFunc関数の方が使いやすく、高速です。 

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

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true. That is, Search requires that f is false for some (possibly empty) prefix of the input range [0, n) and then true for the (possibly empty) remainder; Search returns the first true index. If there is no such index, Search returns n. (Note that the "not found" return value is not -1 as in, for instance, strings.Index.) Search calls f(i) only for i in the range [0, n).

A common use of Search is to find the index i for a value x in a sorted, indexable data structure such as an array or slice. In this case, the argument f, typically a closure, captures the value to be searched for, and how the data structure is indexed and ordered.

For instance, given a slice data sorted in ascending order, the call Search(len(data), func(i int) bool { return data[i] >= 23 }) returns the smallest index i such that data[i] >= 23. If the caller wants to find whether 23 is in the slice, it must test data[i] == 23 separately.

Searching data sorted in descending order would use the <= operator instead of the >= operator.

To complete the example above, the following code tries to find the value x in an integer slice data sorted in ascending order: 

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
	// x is present at data[i]
} else {
	// x is not present in data,
	// but i is the index where it would be inserted.
}

As a more whimsical example, this program guesses your number: 

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)
}
Example (DescendingOrder)

この例では、降順でソートされたリストを検索する方法が示されています。 アプローチは昇順でリストを検索するのと同じですが、条件が逆転しています。 

package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
	x := 6

	i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
	if i < len(a) && a[i] == x {
		fmt.Printf("found %d at index %d in %v\n", x, i, a)
	} else {
		fmt.Printf("%d not found in %v\n", x, a)
	}
}

Output:
found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]

func SearchFloat64s 

func SearchFloat64s(a []float64, x float64) int

SearchFloat64s searches for x in a sorted slice of float64s and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

Example

この例は、昇順に並べられたリストで float64 を検索する方法を示しています。 

package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	a := []float64{1.0, 2.0, 3.3, 4.6, 6.1, 7.2, 8.0}

	x := 2.0
	i := sort.SearchFloat64s(a, x)
	fmt.Printf("found %g at index %d in %v\n", x, i, a)

	x = 0.5
	i = sort.SearchFloat64s(a, x)
	fmt.Printf("%g not found, can be inserted at index %d in %v\n", x, i, a)
}

Output:
found 2 at index 1 in [1 2 3.3 4.6 6.1 7.2 8]
0.5 not found, can be inserted at index 0 in [1 2 3.3 4.6 6.1 7.2 8]

func SearchInts 

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

SearchInts searches for x in a sorted slice of ints and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

Example

この例では、昇順に並べられたリスト内でintを検索する方法を示しています。 

package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	a := []int{1, 2, 3, 4, 6, 7, 8}

	x := 2
	i := sort.SearchInts(a, x)
	fmt.Printf("found %d at index %d in %v\n", x, i, a)

	x = 5
	i = sort.SearchInts(a, x)
	fmt.Printf("%d not found, can be inserted at index %d in %v\n", x, i, a)
}

Output:
found 2 at index 1 in [1 2 3 4 6 7 8]
5 not found, can be inserted at index 4 in [1 2 3 4 6 7 8]

func SearchStrings 

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

SearchStrings searches for x in a sorted slice of strings and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.

func Slice added in v1.8.0 

func Slice(x any, less func(i, j int) bool)

Sliceは与えられたless関数に基づいてスライスxをソートします。 xがスライスでない場合はパニックを起こします。

このソートは安定していることは保証されません：等しい要素は 元の順序から逆になる場合があります。 安定したソートをするには、SliceStableを使用してください。

less関数は、Interface型のLessメソッドと同様の要件を満たす必要があります。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	people := []struct {
		Name string
		Age  int
	}{
		{"Gopher", 7},
		{"Alice", 55},
		{"Vera", 24},
		{"Bob", 75},
	}
	sort.Slice(people, func(i, j int) bool { return people[i].Name < people[j].Name })
	fmt.Println("By name:", people)

	sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
	fmt.Println("By age:", people)
}

Output:
By name: [{Alice 55} {Bob 75} {Gopher 7} {Vera 24}]
By age: [{Gopher 7} {Vera 24} {Alice 55} {Bob 75}]

func SliceIsSorted added in v1.8.0 

func SliceIsSorted(x any, less func(i, j int) bool) bool

SliceIsSortedは、与えられたless関数に従ってスライスxがソートされているかどうかを報告します。 スライスxがスライスでない場合、パニックを起こします。

func SliceStable added in v1.8.0 

func SliceStable(x any, less func(i, j int) bool)

SliceStableは、与えられた比較関数を使用してスライスxをソートし、等しい要素を元の順序で保持します。 xがスライスでない場合、パニックを起こします。

比較関数は、Interface型のLessメソッドと同じ要件を満たす必要があります。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {

	people := []struct {
		Name string
		Age  int
	}{
		{"Alice", 25},
		{"Elizabeth", 75},
		{"Alice", 75},
		{"Bob", 75},
		{"Alice", 75},
		{"Bob", 25},
		{"Colin", 25},
		{"Elizabeth", 25},
	}

	// 名前でソートし、元の順序を保持します
	sort.SliceStable(people, func(i, j int) bool { return people[i].Name < people[j].Name })
	fmt.Println("By name:", people)

	// 名前の順序を保持しつつ年齢でソートする
	sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age })
	fmt.Println("By age,name:", people)

}

Output:
By name: [{Alice 25} {Alice 75} {Alice 75} {Bob 75} {Bob 25} {Colin 25} {Elizabeth 75} {Elizabeth 25}]
By age,name: [{Alice 25} {Bob 25} {Colin 25} {Elizabeth 25} {Alice 75} {Alice 75} {Bob 75} {Elizabeth 75}]

func Sort 

func Sort(data Interface)

SortはLessメソッドによって決定される昇順でデータをソートします。 data.Lenを1回呼び出してnを決定し、O(n*log(n))回のdata.Lessとdata.Swapを呼び出します。ソートは安定するとは限りません。

注意：多くの場合、よりエルゴノミックで高速なslices.SortFunc関数を使用する方が好ましいです。

func Stable added in v1.2.0 

func Stable(data Interface)

Lessメソッドによって決定される昇順でデータを安定的にソートします。 同じ要素の元の順序を保持します。

data.Lenを1回呼び出してnを決定し、data.LessをO(n*log(n))回呼び出し、 data.SwapをO(n*log(n)*log(n))回呼び出します。

注意: 多くの場合、新しいslices.SortStableFunc関数の方が使いやすく、 より高速に実行されます。

func Strings 

func Strings(x []string)

Stringsは文字列のスライスを昇順でソートします。

注意: より高速に動作する新しいslices.Sort関数の使用を検討してください。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
	sort.Strings(s)
	fmt.Println(s)
}

Output:
[Alpha Bravo Delta Go Gopher Grin]

func StringsAreSorted 

func StringsAreSorted(x []string) bool

StringsAreSortedは、スライスxが昇順に並んでいるかどうかを報告します。

注意：より高速に動作するslices.IsSorted関数を使用することを検討してください。

Types

type Float64Slice 

type Float64Slice []float64

Float64Sliceは、[]float64のデータを増加順に並べ替えるためのインターフェースを実装します。 NaN（非数値）の値は他の値よりも前に並べます。

func (Float64Slice) Len 

func (x Float64Slice) Len() int

func (Float64Slice) Less 

func (x Float64Slice) Less(i, j int) bool

Less関数は、ソートインターフェースの要件に従って、x[i]がx[j]の前に並べられるべきかどうかを報告します。 フロート比較自体は推移的な関係ではありませんことに注意してください：NaN（非数）の値については一貫した順序を報告しません。 このLess関数の実装では、NaN値を他の値よりも前に配置します： 

x[i] < x[j] || (math.IsNaN(x[i]) && !math.IsNaN(x[j]))

func (Float64Slice) Search 

func (p Float64Slice) Search(x float64) int

Search returns the result of applying SearchFloat64s to the receiver and x.

func (Float64Slice) Sort 

func (x Float64Slice) Sort()

Sortは便利なメソッドです：x.Sort()はSort(x)を呼び出します。

func (Float64Slice) Swap 

func (x Float64Slice) Swap(i, j int)

type IntSlice 

type IntSlice []int

IntSlice は、Interface のメソッドを []int にアタッチし、昇順でソートします。

func (IntSlice) Len 

func (x IntSlice) Len() int

func (IntSlice) Less 

func (x IntSlice) Less(i, j int) bool

func (IntSlice) Search 

func (p IntSlice) Search(x int) int

Search returns the result of applying SearchInts to the receiver and x.

func (IntSlice) Sort 

func (x IntSlice) Sort()

Sort は便利なメソッドです: x.Sort() は Sort(x) を呼び出します。

func (IntSlice) Swap 

func (x IntSlice) Swap(i, j int)

type Interface 

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int

	// Less reports whether the element with index i
	// must sort before the element with index j.
	//
	// If both Less(i, j) and Less(j, i) are false,
	// then the elements at index i and j are considered equal.
	// Sort may place equal elements in any order in the final result,
	// while Stable preserves the original input order of equal elements.
	//
	// Less must describe a transitive ordering:
	//  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
	//  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
	//
	// Note that floating-point comparison (the < operator on float32 or float64 values)
	// is not a transitive ordering when not-a-number (NaN) values are involved.
	// See Float64Slice.Less for a correct implementation for floating-point values.
	Less(i, j int) bool

	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

このパッケージのルーチンによって、インタフェースの実装はソート可能です。 メソッドは、整数インデックスによって基礎コレクションの要素を参照します。

func Reverse added in v1.1.0 

func Reverse(data Interface) Interface

Reverseはdataの逆順を返します。

Example 
package main

import (
	"github.com/shogo82148/std/fmt"
	"github.com/shogo82148/std/sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4} // ソートされていない
	sort.Sort(sort.Reverse(sort.IntSlice(s)))
	fmt.Println(s)
}

Output:
[6 5 4 3 2 1]

type StringSlice 

type StringSlice []string

StringSliceはInterfaceのメソッドを[]stringに追加し、昇順でソートします。

func (StringSlice) Len 

func (x StringSlice) Len() int

func (StringSlice) Less 

func (x StringSlice) Less(i, j int) bool

func (StringSlice) Search 

func (p StringSlice) Search(x string) int

Search returns the result of applying SearchStrings to the receiver and x.

func (StringSlice) Sort 

func (x StringSlice) Sort()

Sort は利便性のためのメソッドです: x.Sort() は Sort(x) を呼び出します。

func (StringSlice) Swap 

func (x StringSlice) Swap(i, j int)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.