Trier une slice en Golang : slices.Sort, SortFunc et plusieurs champs

Trier les types intégrés

slices.Sort trie toute slice dont le type d'élément est ordonné : entiers, flottants et chaînes. Elle trie sur place et ne renvoie rien.

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

Sortie :

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

Les chaînes se trient par octets, donc chaque lettre ASCII majuscule vient avant chaque lettre minuscule. C'est rarement ce qu'un utilisateur attend pour des noms. La section suivante corrige cela.

Le package slices est arrivé avec Go 1.21. Son Sort est un pattern-defeating quicksort : O(n log n), sur place, et non stable.

Un ordre personnalisé avec SortFunc

slices.SortFunc prend une fonction de comparaison func(a, b T) int. Renvoyez un nombre négatif quand a doit venir en premier, un nombre positif quand c'est b, et zéro quand ils sont égaux. La fonction cmp.Compare renvoie exactement cela pour les types ordonnés.

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 dans une comparaison alloue une nouvelle chaîne chaque fois que son entrée contient une majuscule, et la comparaison s'exécute environ n log n fois. Pour de grosses slices, calculez les clés en minuscules une seule fois. Pour des noms dans d'autres langues (accents, règles locales), utilisez golang.org/x/text/collate, qui est hors de la bibliothèque standard.

Une fonction de comparaison doit être cohérente : si elle dit que a vient avant b, elle doit dire que b vient après a. Une fonction qui enfreint cette règle (par exemple en renvoyant -1 dès que deux valeurs diffèrent) produit une slice mal ordonnée sans aucune erreur. Soustraire des entiers (return a - b) paraît élégant mais déborde pour les grandes valeurs ; utilisez cmp.Compare.

Trier des structs

La fonction de comparaison reçoit des éléments, donc trier des structs selon un champ est le même appel :

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

Les employés avec des salaires égaux peuvent sortir dans n'importe quel ordre ici, parce que SortFunc n'est pas stable. Si vous avez besoin d'un ordre garanti, départagez avec d'autres champs ou utilisez un tri stable.

Trier sur plusieurs champs

Comparez d'abord le champ le plus important et ne passez au suivant qu'en cas d'égalité. cmp.Or (Go 1.22) renvoie son premier argument non nul, ce qui ramène le tout à une ligne :

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

Sortie :

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

Chaque comparaison est évaluée même quand la première tranche, puisque ce sont de simples arguments. Cela coûte peu pour des comparaisons de champs. Quand un critère de départage est coûteux, écrivez à la main la chaîne if c := ...; c != 0 { return c }.

Tri stable

Un tri stable garde dans leur ordre d'origine les éléments qui se comparent égaux. Cela compte quand l'entrée a déjà un ordre significatif, par exemple des enregistrements triés par date que vous regroupez maintenant par utilisateur.

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

Ce code affiche [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}] : pour chaque utilisateur, la séquence d'origine est conservée. Le tri stable demande plus de travail, donc ne l'utilisez que lorsque l'ordre des éléments égaux compte.

Trier une map

Les maps n'ont pas d'ordre. Pour afficher une map triée par clé, triez ses clés : slices.Sorted(maps.Keys(m)) (Go 1.23). Pour trier par valeur, triez les clés avec une comparaison qui consulte les valeurs :

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

Le départage sur le mot compte : sans lui, chan et slice (tous deux à 7) s'afficheraient dans un ordre différent d'une exécution à l'autre, parce que les clés sortent de la map dans un ordre aléatoire. Voir les maps pour en savoir plus.

Le package sort : sort.Slice et compagnie

Avant Go 1.21, le tri passait par le package sort. Vous le verrez dans beaucoup de code existant :

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

Les différences à connaître :

Un bug courant avec sort.Slice consiste à capturer une autre slice que celle qu'on trie, puisque la fonction less indexe par position. SortFunc ne peut pas avoir ce bug car elle vous donne les éléments.

Le type sort.Interface (Len, Less, Swap) est la forme la plus ancienne. C'est encore la façon de trier des données qui ne forment pas une seule slice, comme deux slices parallèles qui doivent bouger ensemble. Depuis Go 1.22, sort.Ints, sort.Strings et sort.Float64s appellent simplement slices.Sort.

Erreurs courantes

• S'attendre à ce que Sort renvoie la slice triée. Elle trie sur place et ne renvoie rien. Utilisez slices.Sorted(slices.Values(s)) si vous voulez une nouvelle slice triée, ou slices.Clone d'abord.
• Supposer que les éléments égaux gardent leur ordre. Seules les variantes Stable le promettent.
• Soustraire pour comparer. a - b déborde. Utilisez cmp.Compare.
• Trier des flottants contenant NaN. cmp.Compare place NaN avant toutes les autres valeurs, ce qui garde le tri cohérent. Une comparaison a < b écrite à la main, non.