🚀 Aula 43 - Tutorial Golang - Ordenação de Slices em Go
Código da aula: Github
Introdução ao Pacote sort
O pacote sort do Go fornece funções e métodos para ordenar slices de diversos tipos de dados, como números inteiros, strings e structs personalizadas.
Essa aula abordará os conceitos básicos de ordenação em Go, utilizando o pacote sort para ordenar slices de diferentes tipos.
Interface sort.Interface
Para que um tipo de dado possa ser ordenado com o pacote sort, ele precisa implementar a interface sort.Interface. Esta interface requer três métodos:- Len() int: Retorna o tamanho da slice.
- Less(i, j int) bool: Compara os elementos nos índices i e j e retorna true se o elemento i deve vir antes do elemento j na ordem final.
- Swap(i, j int): Troca os elementos nos índices i e j de posição. Ao implementar estes métodos, você define como o pacote sort deve comparar e ordenar os elementos do slice.
Funções de Ordenação Pré-definidas
O pacote sort oferece funções pré-definidas para ordenar slices de tipos comuns:- sort.Ints(): Ordena slices de int.
- sort.Strings(): Ordena slices de string.
- sort.Float64s(): Ordena slices de float64.
Ordenação Personalizada
Para tipos de dados com critérios de ordenação específicos, é necessário implementar uma função de comparação personalizada. Esta função deve seguir a mesma lógica do método Less() da interface sort.Interface. Após definir a função de comparação, você pode usar a função sort.Sort() para ordenar o slice, passando a função personalizada como argumento.Aplicações da Ordenação
A ordenação de slices é útil em diversos cenários, como:- Organizar dados para exibição ou análise.
- Filtrar resultados de buscas.
- Implementar algoritmos que exigem dados ordenados.
- Melhorar a eficiência de outras operações.
Conceitos Adicionais
Restrição Ordered: A restrição genérica Ordered permite trabalhar com qualquer tipo que suporte os operadores de comparação (<, <=, >=, >), como números e strings. As funções de ordenação do pacote sort são genéricas e funcionam com qualquer tipo que atenda a esta restrição. Verificação de Ordenação: Embora não exista um pacote padrão para verificar se um slice já está ordenado, você pode implementar esta funcionalidade manualmente iterando pelo slice e comparando elementos adjacentes.Implementação Interna
O pacoteslices tem as funções Sort e SortFunc, essas funções utilizam internamente o mesmo algoritmo de ordenação que o pacote sort tradicionalmente usa.
Esse algoritmo é uma variação do quicksort chamada introsort, ou introspective sort.
O quicksort é conhecido por sua eficiência em muitos casos práticos, sendo um dos algoritmos de ordenação mais rápidos para uso geral.
No entanto, tem uma vulnerabilidade em determinadas configurações de dados, por exemplo, em dados quase ordenados ou quando todos os elementos são iguais, o quicksort pode ter um desempenho muito pior, chegando a uma complexidade de tempo O(n²), o que é consideravelmente lento para grandes conjuntos de dados.
Para mitigar esse problema, o introsort foi desenvolvido.
Veja como acontece:
- Início com Quicksort: O introsort começa usando o quicksort para tentar aproveitar sua rapidez em casos médios.
- Monitoramento da Profundidade: Ele monitora a profundidade da recursão do quicksort. A profundidade máxima permitida geralmente é logarítmica em relação ao número de elementos (log n). Se o algoritmo perceber que a profundidade da recursão está excedendo um limite crítico sem terminar (indicando que está indo em direção à complexidade O(n²)), ele intervém.
- Mudança para Heapsort: Neste ponto, se a complexidade parece estar se deteriorando, o introsort muda para o heapsort. O heapsort é um pouco mais lento que o quicksort em casos médios, mas possui uma complexidade de tempo garantida de O(n log n) no pior caso, independentemente dos dados de entrada. Isso impede que a ordenação se torne ineficientemente lenta.
- Finalização com Insertion Sort: Para conjuntos de dados muito pequenos, o introsort pode finalizar com insertion sort, que é eficiente para pequenas quantidades de elementos devido ao seu baixo custo adicional de operação e simplicidade.
Considerações Finais
O pacote sort é uma ferramenta poderosa para trabalhar com slices em Go. Ele facilita a ordenação de dados de diversos tipos, tornando o código mais organizado e eficiente. Explore a documentação do pacote e os recursos adicionais para aprofundar seu conhecimento sobre ordenação.Exemplos práticos
Vamos ver alguns exemplos práticos de ordenação. OrdenaçãoGenérica: Esse exemplo demonstra uma ordenação genérica com slices.Sort() para strings e inteiros, além de verificar a ordenação usando slices.IsSorted(), destacando a versatilidade do pacote slices para lidar com diferentes tipos de dados.
package main
import (
"fmt"
"slices"
)
func main() {
// Sorting functions are generic, and work for any
// _ordered_ built-in type. For a list of ordered
// types, see [cmp.Ordered](https://pkg.go.dev/cmp#Ordered).
strs := []string{"c", "a", "b"}
slices.Sort(strs)
fmt.Println("Strings:", strs)
// An example of sorting `int`s.
ints := []int{7, 2, 4}
slices.Sort(ints)
fmt.Println("Ints: ", ints)
// We can also use the `slices` package to check if
// a slice is already in sorted order.
s := slices.IsSorted(ints)
fmt.Println("Sorted: ", s)
}package main
import (
"fmt"
"slices"
"time"
)
func main() {
datas := []time.Time{
time.Date(2023, time.December, 10, 0, 0, 0, 0, time.UTC),
time.Date(2024, time.January, 5, 0, 0, 0, 0, time.UTC),
time.Date(2024, time.July, 20, 0, 0, 0, 0, time.UTC),
}
slices.SortFunc(datas, func(a, b time.Time) int {
if a.Equal(b) {
return 0
}
if a.Before(b) {
return -1
}
return 1
})
fmt.Println("Datas ordenadas:", datas)
}
package main
import (
"fmt"
"slices"
)
type Pessoa struct {
Nome string
Idade int
}
func main() {
pessoas := []Pessoa{
{"Maria", 30},
{"João", 25},
{"Ana", 28},
}
// Ordenando por idade
slices.SortFunc(pessoas, func(a, b Pessoa) int {
return a.Idade - b.Idade // Retorna negativo se a < b, zero se a == b, positivo se a > b
})
fmt.Println("Pessoas ordenadas por idade:", pessoas)
// Ordenando por nome
slices.SortFunc(pessoas, func(a, b Pessoa) int {
if a.Nome < b.Nome { return -1 } else if a.Nome > b.Nome {
return 1
}
return 0
})
fmt.Println("Pessoas ordenadas por nome:", pessoas)
}
package main
import (
"fmt"
"slices"
)
type Produto struct {
Nome string
Preço float64
}
func main() {
produtos := []Produto{
{"Caderno", 7.50},
{"Caneta", 3.75},
{"Mochila", 56.90},
}
// Ordenando por preço
slices.SortFunc(produtos, func(a, b Produto) int {
if a.Preço < b.Preço { return -1 } else if a.Preço > b.Preço {
return 1
}
return 0
})
fmt.Println("Produtos ordenados por preço:", produtos)
// Ordenando por nome
slices.SortFunc(produtos, func(a, b Produto) int {
if a.Nome < b.Nome { return -1 } else if a.Nome > b.Nome {
return 1
}
return 0
})
fmt.Println("Produtos ordenados por nome:", produtos)
}
