Menu Close

Sort slices in Go

Johannes Malsam

Sorting collections is a standard task in every programming language. In this article, we’re going to cover the three ways to sort slices in Go.

Prerequisites

Sort int, float64 and string slices

The Go core has functions to sort int, float64 and string slices:

int_slice := []int{3, 2, 4, 2}
sort.Ints(int_slice)
fmt.Println(int_slice)
/// [2 2 3 4]

Sort with comparator function

The function sort.Slice sorts a slice with a function less(i, j int) bool. With sort.StableSlice you can sort a slice with stable order of equal elements.

package main

import (
	"fmt"
	"sort"
)

func main() {
	products := []struct {
		Name  string
		Price float64
	}{
		{"Microphone", 10.0},
		{"Mouse", 20.0},
		{"Keyboard", 20.0},
		{"Headphone", 15.0},
	}

	// Sort by price ascending
	sort.Slice(products, func(i, j int) bool {
		return products[i].Price < products[j].Price
	})
	fmt.Println("Products sorted by price ascending:")
	fmt.Println(products)
	// [{Microphone 10} {Headphone 15} {Mouse 20} {Keyboard 20}]

	// Sort by price descending
	sort.Slice(products, func(i, j int) bool {
		return products[i].Price > products[j].Price
	})
	fmt.Println("Products sorted by price descending:")
	fmt.Println(products)
	// [{Mouse 20} {Keyboard 20} {Headphone 15} {Microphone 10}]
}

Sort with custom data structure

With the function sort.Sort you can sort custom collection types, that implement sort.Interface.

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

Let’s see how this works with the products type:

type Product struct {
	Name  string
	Price float64
}

// Define a custom slice type
type ProductsByPrice []Product

// Implement sort.Interface
func (p ProductsByPrice) Len() int {
	return len(p)
}

// The Less function is just like the comparator function above
func (p ProductsByPrice) Less(i, j int) bool {
	return p[i].Price < p[j].Price
}

// Function to swap two elements in a slice
func (p ProductsByPrice) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func main() {
	productsByPrice := ProductsByPrice{
		{"Microphone", 10.0},
		{"Mouse", 20.0},
		{"Keyboard", 20.0},
		{"Headphone", 15.0},
	}
	
	sort.Sort(productsByPrice)
	fmt.Println(productsByPrice)
	// [{Microphone 10} {Headphone 15} {Mouse 20} {Keyboard 20}]
}

A linear search with complexity O(n) is the best way to find an element in an unsorted slice. One advantage of a sorted slice is that you can perform binary search algorithms, which have a complexity of O(logn). This is great for multiple search operations on a slice with many elements.

Search for int, float64 and string slices

Use the functions:

float_slice := []float64{3.0, 2.0, 4.0, 2.0}
sort.Float64s(float_slice)
index := sort.SearchFloat64s(float_slice, 4)
fmt.Printf("Number %v found at index: %v\n", 4, index)

Search with custom function

The function sort.Search(n int, f (int) bool) works different compared to search functions in most other programming languages:

  • It returns the smallest index in the range [0, n at which f(i) returns true
    • For n = 10 sort.Search will call f with values between 0, 9
    • To find an element out of all slice elements n equals typically len(slice)
    • It returns n if f wasn’t true for any index in the range [0, n]
  • The function f is typically a closure
    • for ascending sorted slices f(i) should return true if slice[i] >= value to be searched for
    • for descending sorted slices f(i) should return true if slice[i] <= value to be searched for

Again: sort.Search returns the smallest index with a value >= (ascending) or <= (descending) than the searched value. There is no guaranty that this is an exact match. To find an exact match, you have to test slice[index] == value.

package main

import (
	"fmt"
	"sort"
)

func main() {
	products := []struct {
		Name  string
		Price int
	}{
		{"Microphone", 10},
		{"Mouse", 20},
		{"Keyboard", 20},
		{"Headphone", 15},
	}
	searchFor := 20

	// ascending sort and search
	sort.Slice(products, func(i, j int) bool {
		return products[i].Price < products[j].Price
	})
	fmt.Println(products)
	// [{Microphone 10} {Headphone 15} {Mouse 20} {Keyboard 20}]
	index := sort.Search(len(products), func(i int) bool {
		return products[i].Price >= searchFor
	})
	// Test for exact match
	if index < len(products) && products[index].Price == searchFor {
		fmt.Printf("Product with price %v found at index: %v\n", searchFor, index)
		//Product with price 20 found at index: 2
	} else {
		fmt.Printf("Value not found\n")
	}

	// descending sort and search
	sort.Slice(products, func(i, j int) bool {
		return products[i].Price > products[j].Price
	})
	fmt.Println(products)
	// [{Mouse 20} {Keyboard 20} {Headphone 15} {Microphone 10}]
	index = sort.Search(len(products), func(i int) bool {
		return products[i].Price <= searchFor
	})
	if index < len(products) && products[index].Price == searchFor {
		fmt.Printf("Product with price %v found at index: %v\n", searchFor, index)
		//Product with price 20 found at index: 2
	} else {
		fmt.Printf("Value not found\n")
	}
}
Tagged , , ,