Documentation
¶
Overview ¶
Package sort provides a generic implementation of the standard library sort package primitives for sorting slices and user-defined collections.
It should be noted that even with generics, some limitations remain on operations such as sorting based on data type, e.g. While any Comparable type can be uniquely identified, used as map keys, or compared with operators, only Ordered types can be sorted.
Of the Go built-in types, the only Ordered types are ints, uints, uintptr, floats, and strings. Including user defined types in the sorting constraint infers that they must be ordered in some way. A user-defined interface is provided that must be implemented by any user-defined type in order for it to implement the algorithms in the sort package.
The basic interface implemented is:
type Sorter 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.
// More details can be found in the standard
// library sort package documentation ...
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
Index ¶
- func Float64s(x []float64)
- func Float64sAreSorted(x []float64) bool
- func Ints(x []int)
- func IntsAreSorted(x []int) bool
- func IsSorted(data Interface) 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 Sorter
- type StringSlice
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Float64s ¶
func Float64s(x []float64)
Float64s sorts a slice of float64s in increasing order. Not-a-number (NaN) values are ordered before other values.
func Float64sAreSorted ¶
Float64sAreSorted reports whether the slice x is sorted in increasing order, with not-a-number (NaN) values before any other values.
func IntsAreSorted ¶
IntsAreSorted reports whether the slice x is sorted in increasing order.
func Sort ¶
func Sort(data Interface)
Sort 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 Stable ¶
func Stable(data Interface)
Stable 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.
func StringsAreSorted ¶
StringsAreSorted reports whether the slice x is sorted in increasing order.
Types ¶
type Float64Slice ¶
type Float64Slice []float64
Float64Slice implements Interface for a []float64, sorting in increasing order, with not-a-number (NaN) values ordered before other values.
func (Float64Slice) Len ¶
func (x Float64Slice) Len() int
func (Float64Slice) Less ¶
func (x Float64Slice) Less(i, j int) bool
Less reports whether x[i] should be ordered before x[j], as required by the sort Interface. Note that floating-point comparison by itself is not a transitive relation: it does not report a consistent ordering for not-a-number (NaN) values. This implementation of Less places NaN values before any others, by using:
x[i] < x[j] || (math.IsNaN(x[i]) && !math.IsNaN(x[j]))
func (Float64Slice) Sort ¶
func (x Float64Slice) Sort()
Sort is a convenience method: x.Sort() calls Sort(x).
func (Float64Slice) Swap ¶
func (x 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 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)
}
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 Sorter ¶
type Sorter[K constraints.Ordered, V any] 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. // More details can be found in the standard // library sort package documentation ... Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) }
An implementation of the standard library sort.Interface that can be sorted by the routines in this package.
type StringSlice ¶
type StringSlice []string
StringSlice attaches the methods of Interface to []string, sorting in increasing order.
func (StringSlice) Len ¶
func (x StringSlice) Len() int
func (StringSlice) Less ¶
func (x StringSlice) Less(i, j int) bool
func (StringSlice) Sort ¶
func (x StringSlice) Sort()
Sort is a convenience method: x.Sort() calls Sort(x).
func (StringSlice) Swap ¶
func (x StringSlice) Swap(i, j int)
Source Files