Golang Slice sortieren: slices.Sort, SortFunc, mehrere Felder

Eingebaute Typen sortieren

slices.Sort sortiert jeden Slice, dessen Elementtyp geordnet ist: Ganzzahlen, Floats und Strings. Es sortiert direkt im Slice und gibt nichts zurück.

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

Ausgabe:

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

Strings werden nach Bytes sortiert, also kommt jeder ASCII-Großbuchstabe vor jedem Kleinbuchstaben. Bei Namen erwartet ein Nutzer das selten. Der nächste Abschnitt behebt das.

Das Paket slices kam mit Go 1.21. Sein Sort ist ein Pattern-Defeating Quicksort: O(n log n), direkt im Slice und nicht stabil.

Eigene Reihenfolge mit SortFunc

slices.SortFunc nimmt eine Vergleichsfunktion func(a, b T) int. Gib eine negative Zahl zurück, wenn a zuerst kommen soll, eine positive, wenn b zuerst kommen soll, und null, wenn beide gleich sind. Der Helfer cmp.Compare liefert genau das für geordnete Typen.

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 in einem Vergleich legt jedes Mal einen neuen String an, wenn die Eingabe einen Großbuchstaben enthält, und der Vergleich läuft etwa n log n Mal. Bei großen Slices berechnest du die kleingeschriebenen Schlüssel einmal vorab. Für Namen in anderen Sprachen (Akzente, Regeln des Gebietsschemas) nimm golang.org/x/text/collate, das außerhalb der Standardbibliothek liegt.

Eine Vergleichsfunktion muss konsistent sein: Sagt sie, dass a vor b kommt, muss sie auch sagen, dass b nach a kommt. Eine Funktion, die das verletzt (zum Beispiel immer -1 zurückgibt, wenn sich zwei Werte unterscheiden), erzeugt einen falsch sortierten Slice ohne jeden Fehler. Ganzzahlen zu subtrahieren (return a - b) sieht elegant aus, läuft aber bei großen Werten über; nimm cmp.Compare.

Structs sortieren

Die Vergleichsfunktion bekommt Elemente, also ist das Sortieren von Structs nach einem Feld derselbe Aufruf:

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

Mitarbeiter mit gleichem Gehalt können hier in beliebiger Reihenfolge herauskommen, weil SortFunc nicht stabil ist. Brauchst du eine garantierte Reihenfolge, löse Gleichstände mit weiteren Feldern auf oder nimm eine stabile Sortierung.

Nach mehreren Feldern sortieren

Vergleiche zuerst das wichtigste Feld und geh nur bei Gleichstand zum nächsten. cmp.Or (Go 1.22) gibt sein erstes Argument ungleich null zurück und macht daraus eine Zeile:

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

Ausgabe:

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

Jeder Vergleich wird ausgewertet, auch wenn schon der erste entscheidet, da es gewöhnliche Argumente sind. Bei Feldvergleichen kostet das wenig. Ist ein Tie-Breaker teuer, schreib die Kette if c := ...; c != 0 { return c } von Hand.

Stabile Sortierung

Eine stabile Sortierung lässt Elemente, die als gleich gelten, in ihrer ursprünglichen Reihenfolge. Das zählt, wenn die Eingabe schon eine sinnvolle Reihenfolge hat, zum Beispiel nach Zeit sortierte Datensätze, die du jetzt nach Nutzer gruppierst.

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

Das gibt [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}] aus: Innerhalb jedes Nutzers bleibt die ursprüngliche Folge erhalten. Stabiles Sortieren macht mehr Arbeit, also nutz es nur, wenn die Reihenfolge gleicher Elemente zählt.

Eine Map sortieren

Maps haben keine Reihenfolge. Um eine Map nach Schlüssel sortiert anzuzeigen, sortierst du ihre Schlüssel: slices.Sorted(maps.Keys(m)) (Go 1.23). Um nach Wert zu sortieren, sortier die Schlüssel mit einem Vergleich, der die Werte nachschlägt:

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

Der Tie-Breaker auf dem Wort zählt: Ohne ihn würden chan und slice (beide 7) von Lauf zu Lauf in anderer Reihenfolge erscheinen, weil die Schlüssel in zufälliger Reihenfolge aus der Map kommen. Mehr dazu unter Maps.

Das Paket sort: sort.Slice und Verwandte

Vor Go 1.21 lief das Sortieren über das Paket sort. Du siehst es in viel bestehendem Code:

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

Unterschiede, die du kennen solltest:

Ein häufiger Bug bei sort.Slice ist, in der Closure einen anderen Slice einzufangen als den, der sortiert wird, da die Less-Funktion über Positionen indiziert. SortFunc kann diesen Bug nicht haben, weil es dir die Elemente übergibt.

Der Typ sort.Interface (Len, Less, Swap) ist die älteste Form. Mit ihm sortierst du nach wie vor Daten, die kein einzelner Slice sind, etwa zwei parallele Slices, die sich gemeinsam bewegen müssen. Seit Go 1.22 rufen sort.Ints, sort.Strings und sort.Float64s einfach slices.Sort auf.

Häufige Fehler

• Erwarten, dass Sort den sortierten Slice zurückgibt. Es sortiert direkt im Slice und gibt nichts zurück. Nimm slices.Sorted(slices.Values(s)), wenn du einen neuen sortierten Slice willst, oder vorher slices.Clone.
• Annehmen, dass gleiche Elemente ihre Reihenfolge behalten. Das versprechen nur die Stable-Varianten.
• Zum Vergleichen subtrahieren. a - b läuft über. Nimm cmp.Compare.
• Floats mit NaN sortieren. cmp.Compare ordnet NaN vor jedem anderen Wert ein, und das hält die Sortierung konsistent. Ein selbst geschriebener Vergleich a < b tut das nicht.