sort - ActiveState ActiveGo 1.8
...

Package sort

import "go4.org/sort"
Overview
Index
Examples

Overview ▾

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

This is a copy of the Go standard library's sort package with the addition of some helpers for sorting slices and using func literals to sort, rather than having to create a sorter type. See the additional MakeInterface, SliceSorter, and Slice functions. Discussion of moving such helpers into the standard library is at: 

https://golang.org/issue/16721

Per Go's "no +1 policy", please only leave a comment on that issue if you have something unique to add. Use Github's emoji reactions otherwise.

▾ Example

Code:

people := []Person{
    {Name: "Bob", Age: 31},
    {Name: "John", Age: 42},
    {Name: "Michael", Age: 17},
    {Name: "Jenny", Age: 26},
}

fmt.Println(people)
sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println(people)

Output:

[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.

Code:

package sort_test

import (
    "fmt"
    "sort"
)

// A couple of type definitions to make the units clear.
type earthMass float64
type au float64

// A Planet defines the properties of a solar system object.
type Planet struct {
    name     string
    mass     earthMass
    distance au
}

// By is the type of a "less" function that defines the ordering of its Planet arguments.
type By func(p1, p2 *Planet) bool

// Sort is a method on the function type, By, that sorts the argument slice according to the function.
func (by By) Sort(planets []Planet) {
    ps := &planetSorter{
        planets: planets,
        by:      by, // The Sort method's receiver is the function (closure) that defines the sort order.
    }
    sort.Sort(ps)
}

// planetSorter joins a By function and a slice of Planets to be sorted.
type planetSorter struct {
    planets []Planet
    by      func(p1, p2 *Planet) bool // Closure used in the Less method.
}

// Len is part of sort.Interface.
func (s *planetSorter) Len() int {
    return len(s.planets)
}

// Swap is part of sort.Interface.
func (s *planetSorter) Swap(i, j int) {
    s.planets[i], s.planets[j] = s.planets[j], s.planets[i]
}

// Less is part of sort.Interface. It is implemented by calling the "by" closure in the sorter.
func (s *planetSorter) Less(i, j int) bool {
    return s.by(&s.planets[i], &s.planets[j])
}

var planets = []Planet{
    {"Mercury", 0.055, 0.4},
    {"Venus", 0.815, 0.7},
    {"Earth", 1.0, 1.0},
    {"Mars", 0.107, 1.5},
}

// ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.
func Example_sortKeys() {
    // Closures that order the Planet structure.
    name := func(p1, p2 *Planet) bool {
        return p1.name < p2.name
    }
    mass := func(p1, p2 *Planet) bool {
        return p1.mass < p2.mass
    }
    distance := func(p1, p2 *Planet) bool {
        return p1.distance < p2.distance
    }
    decreasingDistance := func(p1, p2 *Planet) bool {
        return !distance(p1, p2)
    }

    // Sort the planets by the various criteria.
    By(name).Sort(planets)
    fmt.Println("By name:", planets)

    By(mass).Sort(planets)
    fmt.Println("By mass:", planets)

    By(distance).Sort(planets)
    fmt.Println("By distance:", planets)

    By(decreasingDistance).Sort(planets)
    fmt.Println("By decreasing distance:", planets)

    // Output: 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.

Code:

package sort_test

import (
    "fmt"
    "sort"
)

// A Change is a record of source code changes, recording user, language, and delta size.
type Change struct {
    user     string
    language string
    lines    int
}

type lessFunc func(p1, p2 *Change) bool

// multiSorter implements the Sort interface, sorting the changes within.
type multiSorter struct {
    changes []Change
    less    []lessFunc
}

// Sort sorts the argument slice according to the less functions passed to OrderedBy.
func (ms *multiSorter) Sort(changes []Change) {
    ms.changes = changes
    sort.Sort(ms)
}

// OrderedBy returns a Sorter that sorts using the less functions, in order.
// Call its Sort method to sort the data.
func OrderedBy(less ...lessFunc) *multiSorter {
    return &multiSorter{
        less: less,
    }
}

// Len is part of sort.Interface.
func (ms *multiSorter) Len() int {
    return len(ms.changes)
}

// Swap is part of sort.Interface.
func (ms *multiSorter) Swap(i, j int) {
    ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i]
}

// Less is part of sort.Interface. It is implemented by looping along the
// less functions until it finds a comparison that is either Less or
// !Less. Note that it can call the less functions twice per call. We
// could change the functions to return -1, 0, 1 and reduce the
// number of calls for greater efficiency: an exercise for the reader.
func (ms *multiSorter) Less(i, j int) bool {
    p, q := &ms.changes[i], &ms.changes[j]
    // Try all but the last comparison.
    var k int
    for k = 0; k < len(ms.less)-1; k++ {
        less := ms.less[k]
        switch {
        case less(p, q):
            // p < q, so we have a decision.
            return true
        case less(q, p):
            // p > q, so we have a decision.
            return false
        }
        // p == q; try the next comparison.
    }
    // All comparisons to here said "equal", so just return whatever
    // the final comparison reports.
    return ms.less[k](p, q)
}

var changes = []Change{
    {"gri", "Go", 100},
    {"ken", "C", 150},
    {"glenda", "Go", 200},
    {"rsc", "Go", 200},
    {"r", "Go", 100},
    {"ken", "Go", 200},
    {"dmr", "C", 100},
    {"r", "C", 150},
    {"gri", "Smalltalk", 80},
}

// 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.
func Example_sortMultiKeys() {
    // Closures that order the Change structure.
    user := func(c1, c2 *Change) bool {
        return c1.user < c2.user
    }
    language := func(c1, c2 *Change) bool {
        return c1.language < c2.language
    }
    increasingLines := func(c1, c2 *Change) bool {
        return c1.lines < c2.lines
    }
    decreasingLines := func(c1, c2 *Change) bool {
        return c1.lines > c2.lines // Note: > orders downwards.
    }

    // Simple use: Sort by user.
    OrderedBy(user).Sort(changes)
    fmt.Println("By user:", changes)

    // More examples.
    OrderedBy(user, increasingLines).Sort(changes)
    fmt.Println("By user,<lines:", changes)

    OrderedBy(user, decreasingLines).Sort(changes)
    fmt.Println("By user,>lines:", changes)

    OrderedBy(language, increasingLines).Sort(changes)
    fmt.Println("By language,<lines:", changes)

    OrderedBy(language, increasingLines, user).Sort(changes)
    fmt.Println("By language,<lines,user:", changes)

    // Output:
    // 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)

Code:

package sort_test

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 Example_sortWrapper() {
    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)

    // 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)
}

func printOrgans(s []*Organ) {
    for _, o := range s {
        fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
    }
}

Index ▾

Package files

search.go sort.go zfuncversion.go

func Float64s 

func Float64s(a []float64)

Float64s sorts a slice of float64s in increasing order.

func Float64sAreSorted 

func Float64sAreSorted(a []float64) bool

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

Code:

s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)

Output:

[1 2 3 4 5 6]

func IntsAreSorted 

func IntsAreSorted(a []int) bool

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

func IsSorted 

func IsSorted(data Interface) bool

IsSorted reports whether data is sorted. 

func Search(n int, f func(int) bool) int

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 

func SearchFloat64s(a []float64, x float64) int

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 

func SearchInts(a []int, x int) int

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 

func SearchStrings(a []string, x string) int

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 Slice 

func Slice(slice interface{}, less func(i, j int) bool)

Slice sorts the provided slice using less. If the provided interface is not a slice, the function panics. The sort is not stable. For a stable sort, use sort.Stable with sort.SliceSorter.

▾ Example

Code:

people := []Person{
    {Name: "Bob", Age: 31},
    {Name: "John", Age: 42},
    {Name: "Michael", Age: 17},
    {Name: "Jenny", Age: 26},
}

fmt.Println(people)
sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
fmt.Println(people)

Output:

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

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.

To sort slices without creating a type, see Slice.

▾ Example

Code:

package sort_test

import (
    "fmt"

    "go4.org/sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge implements sort.Interface for []Person based on
// the Age field.
type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func ExampleSort() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Sort(ByAge(people))
    fmt.Println(people)

    // Output:
    // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
    // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
}

func Stable 

func Stable(data Interface)

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 Strings 

func Strings(a []string)

Strings sorts a slice of strings in increasing order.

func StringsAreSorted 

func StringsAreSorted(a []string) bool

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

func With 

func With(length int, swap func(i, j int), less func(i, j int) bool)

With sorts data given the provided length, swap, and less functions. The sort is not guaranteed to be stable.

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 

func (p Float64Slice) Search(x float64) int

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

func (Float64Slice) Sort 

func (p Float64Slice) Sort()

Sort is a convenience method.

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 

func (p IntSlice) Search(x int) int

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

func (IntSlice) Sort 

func (p IntSlice) Sort()

Sort is a convenience method.

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 MakeInterface 

func MakeInterface(length int, swap func(i, j int), less func(i, j int) bool) Interface

MakeInterface returns a sort Interface using the provided length and pair of swap and less functions.

func Reverse 

func Reverse(data Interface) Interface

Reverse returns the reverse order for data.

▾ Example

Code:

s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)

Output:

[6 5 4 3 2 1]

func SliceSorter 

func SliceSorter(slice interface{}, less func(i, j int) bool) Interface

SliceSorter returns a sort.Interface to sort the provided slice using the provided less function. If the provided interface is not a slice, the function panics.

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 

func (p StringSlice) Search(x string) int

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

func (StringSlice) Sort 

func (p StringSlice) Sort()

Sort is a convenience method.

func (StringSlice) Swap 

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