Documentation
¶
Overview ¶
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) ¶
Example_sortKeysは、構造体型をプログラム可能なソート基準でソートする手法を示します。
// プラネット構造体を順序付けるクロージャー。
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) ¶
Example_sortMultiKeysは、構造体型を複数のフィールドセットで比較してソートする手法を示します。 "Less"関数を連鎖させ、それぞれが1つのフィールドを比較します。
// 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 ¶
- func Find(n int, cmp func(int) int) (i int, found bool)
- func Float64s(x []float64)
- func Float64sAreSorted(x []float64) bool
- func Ints(x []int)
- func IntsAreSorted(x []int) bool
- func IsSorted(data Interface) bool
- func Search(n int, f func(int) bool) int
- func SearchFloat64s(a []float64, x float64) int
- func SearchInts(a []int, x int) int
- func SearchStrings(a []string, x string) int
- func Slice(x any, less func(i, j int) bool)
- func SliceIsSorted(x any, less func(i, j int) bool) bool
- func SliceStable(x any, less func(i, j int) bool)
- func Sort(data Interface)
- func Stable(data Interface)
- func Strings(x []string)
- func StringsAreSorted(x []string) bool
- type Float64Slice
- type IntSlice
- type Interface
- type StringSlice
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Find ¶ added in v1.19.0
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)
}
Example ¶
この例は、昇順にソートされたリスト内で文字列を検索する方法を示しています。
package main
import (
"github.com/shogo82148/std/fmt"
"github.com/shogo82148/std/sort"
"github.com/shogo82148/std/strings"
)
func main() {
a := []string{"apple", "banana", "lemon", "mango", "pear", "strawberry"}
for _, x := range []string{"banana", "orange"} {
i, found := sort.Find(len(a), func(i int) int {
return strings.Compare(x, a[i])
})
if found {
fmt.Printf("found %s at index %d\n", x, i)
} else {
fmt.Printf("%s not found, would insert at %d\n", x, i)
}
}
}
Output: found banana at index 1 orange not found, would insert at 4
func Float64s ¶
func Float64s(x []float64)
Float64sはfloat64のスライスを昇順でソートします。 NaN(非数)の値は他の値よりも優先的に並べられます。
注意：Go 1.22以降、この関数は単に 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 ¶
Float64sAreSortedは、スライスxが昇順に並んでいるか、NaN（非数値）の値が他の値の前にあるかどうかを報告します。
注意：Go 1.22以降、この関数は単に 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のスライスを昇順にソートします。
注意：Go 1.22以降、この関数は単に 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 ¶
IntsAreSortedは、スライスxが昇順にソートされているかどうかを報告します。
注意：Go 1.22以降、この関数は単に 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 Search ¶
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 ¶
この例は昇順でソートされたリストの検索を示しています。
package main
import (
"github.com/shogo82148/std/fmt"
"github.com/shogo82148/std/sort"
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
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 2 in [1 3 6 10 15 21 28 36 45 55]
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 ¶
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 ¶
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 ¶
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.
Example ¶
This example demonstrates searching for string in a list sorted in ascending order.
package main
import (
"github.com/shogo82148/std/fmt"
"github.com/shogo82148/std/sort"
)
func main() {
a := []string{"apple", "banana", "cherry", "date", "fig", "grape"}
x := "banana"
i := sort.SearchStrings(a, x)
fmt.Printf("found %s at index %d in %v\n", x, i, a)
x = "coconut"
i = sort.SearchStrings(a, x)
fmt.Printf("%s not found, can be inserted at index %d in %v\n", x, i, a)
}
Output: found banana at index 1 in [apple banana cherry date fig grape] coconut not found, can be inserted at index 3 in [apple banana cherry date fig grape]
func Slice ¶ added in v1.8.0
Sliceは与えられたless関数に基づいてスライスxをソートします。 xがスライスでない場合はパニックを起こします。
このソートは安定していることは保証されません：等しい要素は 元の順序から逆になる場合があります。 安定したソートをするには、SliceStable を使用してください。
less関数は、Interface型のLessメソッドと同じ要件を満たす必要があります。
注意：多くの場合、より新しい slices.SortFunc 関数の方が操作性が高く、実行速度も速くなります。
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
SliceIsSortedは、提供されたless関数に従ってスライスxがソートされているかどうかを報告します。 xがスライスでない場合、panicします。
注意：多くの場合、より新しい slices.IsSortedFunc 関数の方が操作性が高く、実行速度も速くなります。
Example ¶
package main
import (
"github.com/shogo82148/std/fmt"
"github.com/shogo82148/std/sort"
)
func main() {
numbers := []int{1, 2, 3, 4, 5, 6}
isSortedAsc := sort.SliceIsSorted(numbers, func(i, j int) bool {
return numbers[i] < numbers[j]
})
fmt.Printf("%v sorted ascending: %t\n", numbers, isSortedAsc)
numbersDesc := []int{6, 5, 4, 3, 2, 1}
isSortedDesc := sort.SliceIsSorted(numbersDesc, func(i, j int) bool {
return numbersDesc[i] > numbersDesc[j]
})
fmt.Printf("%v sorted descending: %t\n", numbers, isSortedDesc)
unsortedNumbers := []int{1, 3, 2, 4, 5}
isSortedUnsorted := sort.SliceIsSorted(unsortedNumbers, func(i, j int) bool {
return unsortedNumbers[i] < unsortedNumbers[j]
})
fmt.Printf("%v unsorted slice sorted: %t\n", unsortedNumbers, isSortedUnsorted)
}
Output: [1 2 3 4 5 6] sorted ascending: true [1 2 3 4 5 6] sorted descending: true [1 3 2 4 5] unsorted slice sorted: false
func SliceStable ¶ added in v1.8.0
SliceStableは、与えられた比較関数を使用してスライスxをソートし、等しい要素を元の順序で保持します。 xがスライスでない場合、パニックを起こします。
less関数は、Interface型のLessメソッドと同じ要件を満たす必要があります。
注意：多くの場合、より新しい slices.SortStableFunc 関数の方が操作性が高く、実行速度も速くなります。
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は文字列のスライスを昇順でソートします。
注意：Go 1.22以降、この関数は単に 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 ¶
StringsAreSortedは、スライスxが昇順に並んでいるかどうかを報告します。
注意：Go 1.22以降、この関数は単に 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) Swap ¶
func (x Float64Slice) Swap(i, j int)
type IntSlice ¶
type IntSlice []int
IntSlice は、Interface のメソッドを []int にアタッチし、昇順でソートします。
func (IntSlice) Search ¶
Search returns the result of applying SearchInts to the receiver and x.
type Interface ¶
このパッケージのルーチンによって、インタフェースの実装はソート可能です。 メソッドは、整数インデックスによって基礎コレクションの要素を参照します。
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