Sorting and Searching with Go's `sort` Package

In this article, we will explore how to use Go's built-in sort package to perform sorting and searching operations efficiently. The sort package provides functions to sort slices and user-defined collections by implementing the sort.Interface.

Sorting Slices

The sort package provides the following functions to sort slices of basic types:

• sort.Ints(slice []int) - sorts a slice of integers in increasing order.
• sort.Strings(slice []string) - sorts a slice of strings in increasing order (lexicographical order).
• sort.Float64s(slice []float64) - sorts a slice of float64 in increasing order.

Let's see how these work with examples.

package main

import (
    "fmt"
    "sort"
)

func main() {
    // Sorting an integer slice
    intSlice := []int{7, 2, 9, 4, 1}
    sort.Ints(intSlice)
    fmt.Println("Sorted integer slice:", intSlice)

    // Sorting a string slice
    stringSlice := []string{"banana", "apple", "pear", "kiwi"}
    sort.Strings(stringSlice)
    fmt.Println("Sorted string slice:", stringSlice)

    // Sorting a float64 slice
    floatSlice := []float64{2.3, 1.4, 3.9, 0.7}
    sort.Float64s(floatSlice)
    fmt.Println("Sorted float64 slice:", floatSlice)
}

Custom Sort Using sort.Interface

For more complex sorting, such as sorting a slice of structs, you need to implement the sort.Interface which consists of the following three methods:

• Len() - returns the length of the collection.
• Less(i, j int) bool - reports whether the element at index i should sort before the element at index j.
• Swap(i, j int) - swaps the elements with indexes i and j.

Here's an example of a custom sort by implementing the sort.Interface to sort a slice of structs.

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

// 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) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func main() {
    people := []Person{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}}
    sort.Sort(ByAge(people))
    fmt.Println("Sorted by Age:", people)
}

Searching with sort.Search

The sort package also provides the sort.Search function, which performs binary search on sorted slices.

Here's how you can use it:

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums := []int{1, 2, 4, 7, 9}
    target := 4

    i := sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
    if i < len(nums) && nums[i] == target {
        fmt.Printf("Found %d at index %d\n", target, i)
    } else {
        fmt.Printf("%d not found\n", target)
    }
}

The sort.Search function requires a function argument that defines the search space. In this example, it helps identify whether the slice's element at an index satisfies the condition (i.e., greater than or equal to the target value), effectively returning the index of the target element if present.