Docs ejecutables de Go: Ordenación

Q: ¿Cómo se ordena un slice en Go?

Para números y strings, llama a slices.Sort(s) (Go 1.21). Ordena en el sitio y de forma ascendente. Para cualquier otra cosa, o para otro orden, usa slices.SortFunc(s, func(a, b T) int { ... }), donde la función devuelve un número negativo si a va antes, positivo si va antes b, y cero si son iguales.

Q: ¿Cómo ordeno un slice en orden descendente en Go?

Intercambia los argumentos en la comparación: slices.SortFunc(s, func(a, b int) int { return cmp.Compare(b, a) }). O bien ordena de forma ascendente y luego llama a slices.Reverse(s).

Q: ¿Cómo ordeno un slice de structs por varios campos en Go?

Compara el primer campo y pasa al siguiente solo cuando sea igual. cmp.Or (Go 1.22) hace exactamente eso: return cmp.Or(cmp.Compare(a.Dept, b.Dept), cmp.Compare(b.Salary, a.Salary), strings.Compare(a.Name, b.Name)) devuelve el primer resultado distinto de cero.

Q: ¿Qué diferencia hay entre sort.Slice y slices.SortFunc?

sort.Slice(s, func(i, j int) bool) es la API antigua: recibe una función less sobre índices y usa reflexión para intercambiar elementos. slices.SortFunc(s, func(a, b T) int) es genérica, se comprueba en compilación, recibe directamente los elementos y es más rápida. El código nuevo debería usar el paquete slices; sort.Slice sigue siendo común en código escrito antes de Go 1.21.

Ordenar tipos integrados

slices.Sort ordena cualquier slice cuyo tipo de elemento sea ordenable: enteros, flotantes y strings. Ordena en el sitio y no devuelve 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)
}

Salida:

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

Los strings se ordenan por bytes, así que cualquier letra ASCII mayúscula va antes que cualquier minúscula. Rara vez es lo que un usuario espera con nombres. La siguiente sección lo arregla.

El paquete slices llegó en Go 1.21. Su Sort es un pattern-defeating quicksort: O(n log n), en el sitio y no estable.

Orden propio con SortFunc

slices.SortFunc recibe una función de comparación func(a, b T) int. Devuelve un número negativo cuando a debe ir antes, un número positivo cuando debe ir antes b, y cero cuando son iguales. La función auxiliar cmp.Compare devuelve exactamente eso para los tipos ordenables.

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 una comparación reserva un string nuevo cada vez que su entrada tiene una mayúscula, y la comparación se ejecuta unas n log n veces. En slices grandes, calcula las claves en minúscula una sola vez. Para nombres en otros idiomas (tildes, reglas de cada idioma), usa golang.org/x/text/collate, que está fuera de la librería estándar.

Una función de comparación tiene que ser coherente: si dice que a va antes que b, tiene que decir que b va después que a. Una que rompa esto (por ejemplo, devolver -1 siempre que dos valores difieran) produce un slice mal ordenado sin ningún error. Restar enteros (return a - b) parece elegante pero desborda con valores grandes; usa cmp.Compare.

Ordenar structs

La función de comparación recibe elementos, así que ordenar structs por un campo es la misma llamada:

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

Los empleados con el mismo salario pueden salir en cualquier orden, porque SortFunc no es estable. Si necesitas un orden garantizado, desempata con más campos o usa una ordenación estable.

Ordenar por varios campos

Compara primero el campo más importante y pasa al siguiente solo si hay empate. cmp.Or (Go 1.22) devuelve su primer argumento distinto de cero, lo que deja esto en una línea:

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

Salida:

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

Todas las comparaciones se evalúan aunque la primera ya decida, porque son argumentos normales. Con comparaciones de campos cuesta poco. Cuando un desempate es caro, escribe a mano la cadena if c := ...; c != 0 { return c }.

Ordenación estable

Una ordenación estable mantiene en su orden original los elementos que se comparan como iguales. Importa cuando la entrada ya tiene un orden con sentido, por ejemplo registros ordenados por tiempo que ahora agrupas por usuario.

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

Esto imprime [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: dentro de cada usuario se conserva la secuencia original. La ordenación estable hace más trabajo, así que úsala solo cuando importe el orden de los elementos iguales.

Ordenar un map

Los maps no tienen orden. Para mostrar un map ordenado por clave, ordena sus claves: slices.Sorted(maps.Keys(m)) (Go 1.23). Para ordenarlo por valor, ordena las claves con una comparación que consulte los 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])
	}
}

El desempate por la palabra importa: sin él, chan y slice (los dos con 7) se imprimirían en un orden distinto en cada ejecución, porque las claves salen del map en orden aleatorio. Consulta maps para más detalles.

El paquete sort: sort.Slice y compañía

Antes de Go 1.21, se ordenaba con el paquete sort. Lo verás en mucho 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 { ... })

Diferencias que conviene conocer:

	`sort.Slice`	`slices.SortFunc`
La función recibe	índices `i, j`	elementos `a, b`
Devuelve	`bool` (si i es menor que j)	`int` (negativo, cero, positivo)
Seguridad de tipos	recibe `any`, usa reflexión	genérica, comprobada en compilación
Velocidad	más lenta	más rápida

Un bug habitual con sort.Slice es que la closure use un slice distinto del que se está ordenando, porque la función less indexa por posición. SortFunc no puede tener ese bug porque te entrega los elementos.

El tipo sort.Interface (Len, Less, Swap) es la forma más antigua. Sigue siendo la manera de ordenar datos que no son un único slice, como dos slices paralelos que tienen que moverse juntos. Desde Go 1.22, sort.Ints, sort.Strings y sort.Float64s simplemente llaman a slices.Sort.

Errores comunes

Esperar que Sort devuelva el slice ordenado. Ordena en el sitio y no devuelve nada. Usa slices.Sorted(slices.Values(s)) si quieres un slice ordenado nuevo, o haz antes slices.Clone.
Suponer que los elementos iguales mantienen su orden. Solo las variantes Stable lo prometen.
Restar para comparar. a - b desborda. Usa cmp.Compare.
Ordenar flotantes con NaN. cmp.Compare coloca NaN antes que cualquier otro valor, lo que mantiene coherente la ordenación. Una comparación a < b escrita a mano no.

Preguntas frecuentes

¿Cómo se ordena un slice en Go?

Para números y strings, llama a slices.Sort(s) (Go 1.21). Ordena en el sitio y de forma ascendente. Para cualquier otra cosa, o para otro orden, usa slices.SortFunc(s, func(a, b T) int { ... }), donde la función devuelve un número negativo si a va antes, positivo si va antes b, y cero si son iguales.

¿Cómo ordeno un slice en orden descendente en Go?

Intercambia los argumentos en la comparación: slices.SortFunc(s, func(a, b int) int { return cmp.Compare(b, a) }). O bien ordena de forma ascendente y luego llama a slices.Reverse(s).

¿Cómo ordeno un slice de structs por varios campos en Go?

Compara el primer campo y pasa al siguiente solo cuando sea igual. cmp.Or (Go 1.22) hace exactamente eso: return cmp.Or(cmp.Compare(a.Dept, b.Dept), cmp.Compare(b.Salary, a.Salary), strings.Compare(a.Name, b.Name)) devuelve el primer resultado distinto de cero.

¿Qué diferencia hay entre sort.Slice y slices.SortFunc?

sort.Slice(s, func(i, j int) bool) es la API antigua: recibe una función less sobre índices y usa reflexión para intercambiar elementos. slices.SortFunc(s, func(a, b T) int) es genérica, se comprueba en compilación, recibe directamente los elementos y es más rápida. El código nuevo debería usar el paquete slices; sort.Slice sigue siendo común en código escrito antes de Go 1.21.

Conceptos relacionados