Ordenar slices em Golang: slices.Sort, SortFunc e vários campos

Ordenando tipos embutidos

slices.Sort ordena qualquer slice cujo tipo de elemento seja ordenável: inteiros, floats e strings. Ele ordena no lugar e não devolve nada.

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

Saída:

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

Strings são ordenadas por bytes, então toda letra ASCII maiúscula vem antes de toda minúscula. Raramente é isso que um usuário espera para nomes. A próxima seção resolve isso.

O pacote slices chegou no Go 1.21. O Sort dele é um pattern-defeating quicksort: O(n log n), no lugar e não estável.

Ordem personalizada com SortFunc

slices.SortFunc recebe uma função de comparação func(a, b T) int. Devolva um número negativo quando a deve vir primeiro, um positivo quando b deve vir primeiro, e zero quando forem iguais. A função auxiliar cmp.Compare devolve exatamente isso para tipos ordenáveis.

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

strings.ToLower dentro de uma comparação aloca uma string nova sempre que a entrada tem uma letra maiúscula, e a comparação executa cerca de n log n vezes. Para slices grandes, calcule as chaves em minúsculas uma vez só. Para nomes em outros idiomas (acentos, regras locais), use golang.org/x/text/collate, que fica fora da biblioteca padrão.

Uma função de comparação precisa ser consistente: se ela diz que a vem antes de b, precisa dizer que b vem depois de a. Uma que quebra isso (por exemplo, devolvendo -1 sempre que dois valores são diferentes) gera um slice ordenado errado, sem nenhum erro. Subtrair inteiros (return a - b) parece elegante, mas estoura com valores grandes; use cmp.Compare.

Ordenando structs

A função de comparação recebe os elementos, então ordenar structs por um campo é a mesma chamada:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

Funcionários com salários iguais podem sair em qualquer ordem aqui, porque o SortFunc não é estável. Se você precisa de uma ordem garantida, desempate com mais campos ou use uma ordenação estável.

Ordenando por vários campos

Compare primeiro o campo mais importante e passe para o próximo só em caso de empate. O cmp.Or (Go 1.22) devolve o seu primeiro argumento diferente de zero, o que transforma isso em uma linha:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

Saída:

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

Todas as comparações são avaliadas mesmo quando a primeira decide, já que são argumentos comuns. Isso custa pouco em comparações de campos. Quando um critério de desempate é caro, escreva à mão a cadeia if c := ...; c != 0 { return c }.

Ordenação estável

Uma ordenação estável mantém na ordem original os elementos que se comparam como iguais. Isso importa quando a entrada já tem uma ordem com significado, por exemplo registros ordenados por horário que você agora agrupa por usuário.

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

Isto imprime [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: dentro de cada usuário, a sequência original sobrevive. A ordenação estável dá mais trabalho, então use-a só quando a ordem dos elementos iguais importar.

Ordenando um map

Maps não têm ordem. Para mostrar um map ordenado pela chave, ordene as chaves: slices.Sorted(maps.Keys(m)) (Go 1.23). Para ordenar pelo valor, ordene as chaves com uma comparação que consulta os valores:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

O desempate pela palavra importa: sem ele, chan e slice (os dois com 7) sairiam em uma ordem diferente a cada execução, porque as chaves saem do map em ordem aleatória. Veja maps para mais detalhes.

O pacote sort: sort.Slice e companhia

Antes do Go 1.21, a ordenação passava pelo pacote sort. Você vai vê-lo em muito código existente:

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

Diferenças que vale a pena conhecer:

Um bug comum com sort.Slice é a closure capturar um slice diferente do que está sendo ordenado, já que a função less indexa por posição. O SortFunc não pode ter esse bug, porque entrega os próprios elementos.

O tipo sort.Interface (Len, Less, Swap) é a forma mais antiga. Ele ainda é o jeito de ordenar dados que não são um único slice, como dois slices paralelos que precisam se mover juntos. Desde o Go 1.22, sort.Ints, sort.Strings e sort.Float64s simplesmente chamam slices.Sort.

Erros comuns

• Esperar que o Sort devolva o slice ordenado. Ele ordena no lugar e não devolve nada. Use slices.Sorted(slices.Values(s)) se quiser um slice novo ordenado, ou slices.Clone antes.
• Supor que elementos iguais mantêm a ordem. Só as variantes Stable prometem isso.
• Subtrair para comparar. a - b estoura. Use cmp.Compare.
• Ordenar floats com NaN. cmp.Compare coloca NaN antes de todos os outros valores, o que mantém a ordenação consistente. Uma comparação a < b escrita à mão não faz isso.