Learn/Go/12. Sorting and searching
Lesson 12 of 15
Sign in

Go, lesson 12

Sorting and searching

Sorted data is easier to read and much faster to search. Go's slices package (with help from the cmp package) gives you everything you need, and it works with any element type.

Sorting basics

slices.Sort sorts numbers and strings into ascending order, in place: it rearranges the slice you give it rather than returning a new one.

Strings sort by byte value, so all uppercase letters come before lowercase ones. For a case-insensitive order, compare lowercased copies (see below).

For descending order, sort and then call slices.Reverse(nums).

Custom order with SortFunc

To sort structs, or to sort in any special way, use slices.SortFunc. You pass a comparison function that receives two elements a and and returns:

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Price check

Press Ctrl Enter or Check to test your code.

b
  • a negative number if a should come first,
  • a positive number if b should come first,
  • zero if they are equal for sorting purposes.

cmp.Compare(x, y) produces exactly that for numbers and strings, so most comparison functions are one line:

For descending order, swap the arguments: cmp.Compare(b.Time, a.Time).

Breaking ties

When two elements compare equal on the main key, add a second key. cmp.Or returns its first non-zero argument, which reads nicely as "compare by this, then by that":

slices.SortFunc is not guaranteed to be stable: equal elements may end up in any order. If you need equal elements to keep their original order, use slices.SortStableFunc.

Searching

slices.Index(s, v) scans from the start and returns the position of v, or -1. That is a linear search: on a list of a million items it may look at all million.

If the slice is sorted, binary search is far faster. It looks at the middle item, decides which half the target must be in, and throws the other half away. A million items take about 20 steps.

When the target is missing, the index tells you where it would be inserted to keep the slice sorted. That makes questions like "how many values are smaller than x?" easy to answer.

For struct slices, slices.BinarySearchFunc takes a comparison between an element and the target. The slice must be sorted by that same key, or the results are meaningless.

Sorting map keys

Recall that maps have no order. To print a map in key order, collect and sort its keys. maps.Keys returns an iterator, and slices.Sorted turns any iterator into a sorted slice:

Further reading

  • Package slices
  • Package cmp
  • Package maps

The first line holds n, the number of players. Each of the next n lines holds a name and a score. Print the leaderboard: highest score first; players with equal scores in alphabetical order of name. Number the lines from 1, as <rank>. <name> <score>.

Sample input:

Sample output:

A shop has a sorted price list. The first line holds n, then n prices in ascending order on one line. The next line holds q, then q queries on one line. For each query price p, print p: found at <index> if it is in the list (indexes start at 0), otherwise p: <k> cheaper where k is how many listed prices are below p. Use binary search.

Sample input:

Sample output:

nums := []int{42, 7, 19}
slices.Sort(nums)
fmt.Println(nums) // [7 19 42]

names := []string{"pear", "Apple", "fig"}
slices.Sort(names)
fmt.Println(names) // [Apple fig pear]
type Runner struct {
	Name string
	Time int // seconds
}

slices.SortFunc(runners, func(a, b Runner) int {
	return cmp.Compare(a.Time, b.Time) // fastest first
})
slices.SortFunc(runners, func(a, b Runner) int {
	return cmp.Or(
		cmp.Compare(a.Time, b.Time),
		cmp.Compare(a.Name, b.Name),
	)
})
sorted := []int{3, 8, 15, 23, 42}
i, found := slices.BinarySearch(sorted, 23)
fmt.Println(i, found) // 3 true

i, found = slices.BinarySearch(sorted, 10)
fmt.Println(i, found) // 2 false
for _, k := range slices.Sorted(maps.Keys(stock)) {
	fmt.Println(k, stock[k])
}
4
zed 50
amy 80
bob 50
cat 95
1. cat 95
2. amy 80
3. bob 50
4. zed 50
5
3 8 15 23 42
3
23 10 50
23: found at 3
10: 2 cheaper
50: 5 cheaper