Documentation
¶
Overview ¶
Package sort provides primitives for sorting slices and user-defined collections.
Index ¶
- func Float64s(a []float64)
- func Float64sAreSorted(a []float64) bool
- func Ints(a []int)
- func IntsAreSorted(a []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 Sort(data Interface)
- func Strings(a []string)
- func StringsAreSorted(a []string) bool
- type Float64Slice
- type IntSlice
- type Interface
- type StringSlice
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64sAreSorted ¶
Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
func Ints ¶
func Ints(a []int)
Ints sorts a slice of ints in increasing order.
Example ¶
package main
import (
"fmt"
"sort"
)
func main() {
s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)
}
Output: [1 2 3 4 5 6]
func IntsAreSorted ¶
IntsAreSorted tests whether a slice of ints is sorted in increasing order.
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)
}
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.
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.
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.
func Sort ¶
func Sort(data Interface)
Sort sorts data. It makes one call to data.Len to determine n, and O(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.
func StringsAreSorted ¶
StringsAreSorted tests whether a slice of strings is sorted in increasing order.
Types ¶
type Float64Slice ¶
type Float64Slice []float64
Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
func (Float64Slice) Len ¶
func (p Float64Slice) Len() int
func (Float64Slice) Less ¶
func (p Float64Slice) Less(i, j int) bool
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 (p Float64Slice) Swap(i, j int)
type IntSlice ¶
type IntSlice []int
IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type Interface ¶
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns whether the element with index i should sort
// before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
A type, typically a collection, that satisfies sort.Interface can be sorted by the routines in this package. The methods require that the elements of the collection be enumerated by an integer index.
Example ¶
package main
import (
"fmt"
"sort"
)
type Grams int
func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }
type Organ struct {
Name string
Weight Grams
}
type Organs []*Organ
func (s Organs) Len() int { return len(s) }
func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
// ByName implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByName struct{ Organs }
func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }
// ByWeight implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByWeight struct{ Organs }
func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }
func main() {
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)
}
func printOrgans(s []*Organ) {
for _, o := range s {
fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
}
}
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)
Example (Reverse) ¶
package main
import (
"fmt"
"sort"
)
// Reverse embeds a sort.Interface value and implements a reverse sort over
// that value.
type Reverse struct {
// This embedded Interface permits Reverse to use the methods of
// another Interface implementation.
sort.Interface
}
// Less returns the opposite of the embedded implementation's Less method.
func (r Reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
func main() {
s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(Reverse{sort.IntSlice(s)})
fmt.Println(s)
}
Output: [6 5 4 3 2 1]
type StringSlice ¶
type StringSlice []string
StringSlice attaches the methods of Interface to []string, sorting in increasing order.
func (StringSlice) Len ¶
func (p StringSlice) Len() int
func (StringSlice) Less ¶
func (p 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) Swap ¶
func (p StringSlice) Swap(i, j int)
Source Files