...
Run Format

Package sort

import "sort"
Overview
Index
Examples

Overview ▾

Package sort provides primitives for sorting slices and user-defined collections.

Example

[Bob: 31 John: 42 Michael: 17 Jenny: 26]
[Michael: 17 Jenny: 26 Bob: 31 John: 42]

Example (SortKeys)

ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.

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)

ExampleMultiKeys demonstrates a technique for sorting a struct type using different sets of multiple fields in the comparison. We chain together "Less" functions, each of which compares a single field.

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} {r Go 100} {gri Go 100} {ken Go 200} {glenda 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)

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)

func Float64s

Float64s sorts a slice of float64s in increasing order.

func Float64s(a []float64)

func Float64sAreSorted

Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.

func Float64sAreSorted(a []float64) bool

func Ints

Ints sorts a slice of ints in increasing order.

func Ints(a []int)

Example

[1 2 3 4 5 6]

func IntsAreSorted

IntsAreSorted tests whether a slice of ints is sorted in increasing order.

func IntsAreSorted(a []int) bool

func IsSorted

IsSorted reports whether data is sorted.

func IsSorted(data Interface) bool

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 Search(n int, f func(int) bool) int

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 SearchFloat64s(a []float64, x float64) int

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 SearchInts(a []int, x int) int

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 SearchStrings(a []string, x string) int

func Sort

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 Sort(data Interface)

func Stable

Stable sorts data 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 Stable(data Interface)

func Strings

Strings sorts a slice of strings in increasing order.

func Strings(a []string)

func StringsAreSorted

StringsAreSorted tests whether a slice of strings is sorted in increasing order.

func StringsAreSorted(a []string) bool

type Float64Slice

Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.

type Float64Slice []float64

func (Float64Slice) Len

func (p Float64Slice) Len() int

func (Float64Slice) Less

func (p Float64Slice) Less(i, j int) bool

func (Float64Slice) Search

Search returns the result of applying SearchFloat64s to the receiver and x.

func (p Float64Slice) Search(x float64) int

func (Float64Slice) Sort

Sort is a convenience method.

func (p Float64Slice) Sort()

func (Float64Slice) Swap

func (p Float64Slice) Swap(i, j int)

type IntSlice

IntSlice attaches the methods of Interface to []int, sorting in increasing order.

type IntSlice []int

func (IntSlice) Len

func (p IntSlice) Len() int

func (IntSlice) Less

func (p IntSlice) Less(i, j int) bool

func (IntSlice) Search

Search returns the result of applying SearchInts to the receiver and x.

func (p IntSlice) Search(x int) int

func (IntSlice) Sort

Sort is a convenience method.

func (p IntSlice) Sort()

func (IntSlice) Swap

func (p IntSlice) Swap(i, j int)

type Interface

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 Interface interface {
        // Len is the number of elements in the collection.
        Len() int
        // Less reports 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)
}

func Reverse

Reverse returns the reverse order for data.

func Reverse(data Interface) Interface

Example

[6 5 4 3 2 1]

type StringSlice

StringSlice attaches the methods of Interface to []string, sorting in increasing order.

type StringSlice []string

func (StringSlice) Len

func (p StringSlice) Len() int

func (StringSlice) Less

func (p StringSlice) Less(i, j int) bool

func (StringSlice) Search

Search returns the result of applying SearchStrings to the receiver and x.

func (p StringSlice) Search(x string) int

func (StringSlice) Sort

Sort is a convenience method.

func (p StringSlice) Sort()

func (StringSlice) Swap

func (p StringSlice) Swap(i, j int)