Documentation
¶
Overview ¶
Package sort provides primitives for sorting arrays and user-defined collections.
Index ¶
- func Float64sAreSorted(a []float64) bool
- 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 SortFloat64s(a []float64)
- func SortInts(a []int)
- func SortStrings(a []string)
- func StringsAreSorted(a []string) bool
- type Float64Array
- type IntArray
- type Interface
- type StringArray
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64sAreSorted ¶
Float64sAreSorted tests whether an array of float64s is sorted in increasing order.
func IntsAreSorted ¶
IntsAreSorted tests whether an array 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. 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 like 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 array 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 array 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 array must be sorted in ascending order.
func SortFloat64s ¶
func SortFloat64s(a []float64)
SortFloat64s sorts an array of float64s in increasing order.
func SortStrings ¶
func SortStrings(a []string)
SortStrings sorts an array of strings in increasing order.
func StringsAreSorted ¶
StringsAreSorted tests whether an array of strings is sorted in increasing order.
Types ¶
type Float64Array ¶
type Float64Array []float64
Float64Array attaches the methods of Interface to []float64, sorting in increasing order.
func (Float64Array) Len ¶
func (p Float64Array) Len() int
func (Float64Array) Less ¶
func (p Float64Array) Less(i, j int) bool
func (Float64Array) Search ¶
func (p Float64Array) Search(x float64) int
Search returns the result of applying SearchFloat64s to the receiver and x.
func (Float64Array) Swap ¶
func (p Float64Array) Swap(i, j int)
type IntArray ¶
type IntArray []int
IntArray 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.
type StringArray ¶
type StringArray []string
StringArray attaches the methods of Interface to []string, sorting in increasing order.
func (StringArray) Len ¶
func (p StringArray) Len() int
func (StringArray) Less ¶
func (p StringArray) Less(i, j int) bool
func (StringArray) Search ¶
func (p StringArray) Search(x string) int
Search returns the result of applying SearchStrings to the receiver and x.
func (StringArray) Swap ¶
func (p StringArray) Swap(i, j int)
Source Files