Documentation
¶
Index ¶
- func Ascend[T Interface](data T)
- func BuiltinAscend[T cmp.FOrdered](data []T)
- func BuiltinCmpFunc[T num.Integer](s []T, i, j int) int
- func BuiltinIsAscend[T cmp.FOrdered](data []T) bool
- func BuiltinLessFunc[T cmp.FOrdered](s []T, i, j int) bool
- func Find(n int, cmp func(int) int) (i int, found bool)
- func FindEx[T any](n int, arg T, cmp func(int, T) int) (i int, found bool)
- func IsAscend[T Interface](data T) bool
- func Search(n int, cmp func(int) bool) int
- func SearchEx[T any](n int, arg T, cmp func(int, T) bool) int
- func SliceAscend[T any](data []T, cmp func(data []T, i, j int) bool)
- func SliceIsAscend[T any](data []T, cmp func(data []T, i, j int) bool) bool
- func SliceStableAscend[T any](data []T, cmp func(data []T, i, j int) bool)
- func StableAscend[T Interface](data T)
- type Interface
- type ReverseSorter
- type SliceSorter
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Ascend ¶
func Ascend[T Interface](data T)
Ascend sorts data in ascending order as determined by the Less method.
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 BuiltinAscend ¶
func BuiltinIsAscend ¶
func Find ¶
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 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 SliceAscend ¶
func SliceStableAscend ¶
func StableAscend ¶
func StableAscend[T Interface](data T)
StableAscend sorts data in ascending order as determined by the Less method, while keeping the original order of equal elements.
It makes one call to data.Len to determine n, O(n*log(n)) calls to data.Less and O(n*log(n)*log(n)) calls to data.Swap.
Types ¶
type Interface ¶
type Interface interface {
// A sortable collection must have finite elements.
iter.Finite
// 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.
// Ascend 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)
}
An implementation of Interface can be sorted by the routines in this package. The methods refer to elements of the underlying collection by integer index.
type ReverseSorter ¶
type ReverseSorter[T Interface] struct { Inner T }
func (ReverseSorter[T]) Less ¶
func (r ReverseSorter[T]) Less(i, j int) bool
Less returns the opposite of the embedded implementation's Less method.
func (ReverseSorter[T]) Swap ¶
func (r ReverseSorter[T]) Swap(i int, j int)
Swap implements Interface
type SliceSorter ¶
func (*SliceSorter[E]) Less ¶
func (s *SliceSorter[E]) Less(i, j int) bool
Less implements Interface
Source Files