Nesta aula, vamos mergulhar no pacote sort da biblioteca padrão de Go, uma ferramenta essencial para organizar dados de forma eficiente. Você aprenderá a ordenar slices de tipos básicos e personalizados, realizar buscas binárias e entender as nuances de estabilidade que afetam o comportamento da ordenação.

Dominar a ordenação é fundamental para muitos algoritmos e operações do dia a dia. O pacote sort fornece funções prontas e interfaces que permitem ordenar praticamente qualquer tipo de dado, com desempenho otimizado e sintaxe limpa.

sort.Slice

A função sort.Slice é a maneira mais simples de ordenar um slice em Go. Ela recebe o slice e uma função de comparação que define a ordem. Essa função deve retornar true se o elemento na posição i deve vir antes do elemento na posição j.

Um dos grandes benefícios do sort.Slice é que ele funciona com qualquer tipo de slice, sem exigir que o tipo implemente uma interface específica. Isso torna a ordenação rápida e direta, especialmente para tipos básicos como inteiros, strings ou estruturas personalizadas.

Vamos ver um exemplo prático ordenando um slice de inteiros e um slice de structs:

package main

import (
    "fmt"
    "sort"
)

type Pessoa struct {
    Nome string
    Idade int
}

func main() {
    // Ordenando inteiros
    numeros := []int{5, 2, 8, 1, 9}
    sort.Slice(numeros, func(i, j int) bool {
        return numeros[i] < numeros[j]
    })
    fmt.Println("Números ordenados:", numeros) // [1 2 5 8 9]

    // Ordenando structs por idade
    pessoas := []Pessoa{
        {"Alice", 30},
        {"Bob", 25},
        {"Carol", 35},
    }
    sort.Slice(pessoas, func(i, j int) bool {
        return pessoas[i].Idade < pessoas[j].Idade
    })
    fmt.Println("Pessoas ordenadas por idade:", pessoas)
}

A função de comparação captura as variáveis do slice por referência, permitindo acessar os elementos diretamente. Isso é conveniente, mas requer cuidado com a captura de variáveis em loops, pois a função pode ser chamada em qualquer momento durante a ordenação.

Interfaces de ordenação

Para tipos que precisam ser ordenados frequentemente, Go oferece a interface sort.Interface. Ela exige a implementação de três métodos: Len(), Less(i, j int) bool e Swap(i, j int). Ao implementar essa interface, você pode usar sort.Sort para ordenar o seu tipo.

Essa abordagem é mais verbosa, mas oferece mais controle e reutilização. Ela também permite que você defina a ordenação como parte do tipo, tornando o código mais expressivo.

Vejamos como implementar a interface para o tipo Pessoa e ordenar por nome:

type PorNome []Pessoa

func (p PorNome) Len() int           { return len(p) }
func (p PorNome) Less(i, j int) bool { return p[i].Nome < p[j].Nome }
func (p PorNome) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func main() {
    pessoas := []Pessoa{
        {"Alice", 30},
        {"Bob", 25},
        {"Carol", 35},
    }
    sort.Sort(PorNome(pessoas))
    fmt.Println("Pessoas ordenadas por nome:", pessoas)
}

Além de sort.Sort, o pacote fornece sort.Stable, que preserva a ordem original de elementos iguais (veremos mais adiante). Também existem atalhos para tipos básicos: sort.Ints, sort.Float64s, sort.Strings.

Busca

O pacote sort também oferece funções de busca binária para slices ordenados. A função sort.Search retorna o menor índice i no qual a função passada retorna true. Para slices de tipos básicos, existem atalhos como sort.SearchInts, sort.SearchFloat64s e sort.SearchStrings.

É importante que o slice esteja ordenado para que a busca binária funcione corretamente. O retorno é o índice onde o elemento deveria ser inserido para manter a ordem.

Exemplo de busca em um slice de inteiros:

numeros := []int{1, 3, 5, 7, 9}
procurado := 5
indice := sort.SearchInts(numeros, procurado)
if indice < len(numeros) && numeros[indice] == procurado {
    fmt.Printf("Encontrado %d no índice %d\n", procurado, indice)
} else {
    fmt.Printf("%d não encontrado, deveria ser inserido em %d\n", procurado, indice)
}

Para busca personalizada, você pode usar sort.Search com uma função que define a condição. Por exemplo, buscar a primeira pessoa com idade maior que 30 em um slice ordenado por idade:

idades := []int{25, 30, 35, 40}
indice := sort.Search(len(idades), func(i int) bool { return idades[i] > 30 })
fmt.Println("Primeira idade > 30 no índice:", indice) // 2

Estável vs instável

A estabilidade de um algoritmo de ordenação refere-se à manutenção da ordem relativa de elementos com chaves iguais. Um algoritmo estável garante que, se dois elementos têm a mesma chave, a ordem original é preservada. Algoritmos instáveis podem trocá-los.

Em Go, sort.Slice e sort.Sort usam um algoritmo instável (quicksort variante), enquanto sort.SliceStable e sort.Stable usam um algoritmo estável (merge sort). A estabilidade é importante quando você ordena por múltiplos critérios em sequência.

Por exemplo, se você ordenar uma lista de pessoas primeiro por nome e depois por idade, com um algoritmo estável, a ordenação por idade preservará a ordem por nome para pessoas com a mesma idade. Com um algoritmo instável, isso pode não acontecer.

A escolha entre estável e instável envolve um trade-off: algoritmos estáveis costumam ser um pouco mais lentos e usar mais memória, mas garantem a preservação da ordem. Para a maioria dos casos, a versão instável é suficiente, mas quando a ordem relativa importa, use a estável.

Exemplo demonstrando a diferença:

type Item struct {
    Categoria string
    Valor     int
}

itens := []Item{
    {"A", 1},
    {"B", 1},
    {"A", 2},
}

// Ordenar por valor (instável)
sort.Slice(itens, func(i, j int) bool { return itens[i].Valor < itens[j].Valor })
fmt.Println("Instável:", itens) // Pode trocar a ordem dos itens com valor 1

itens2 := []Item{
    {"A", 1},
    {"B", 1},
    {"A", 2},
}

// Ordenar por valor (estável)
sort.SliceStable(itens2, func(i, j int) bool { return itens2[i].Valor < itens2[j].Valor })
fmt.Println("Estável:", itens2) // Mantém a ordem original: A, B, A

Boas práticas

Ao trabalhar com ordenação em Go, considere as seguintes recomendações:

  • Use sort.Slice para ordenações rápidas e pontuais, especialmente em funções pequenas.
  • Implemente sort.Interface quando o tipo for usado em múltiplos lugares ou quando você quiser encapsular a lógica de ordenação.
  • Prefira sort.SliceStable quando a ordem de elementos iguais for relevante.
  • Para buscar em slices ordenados, use as funções de busca binária para eficiência O(log n).
  • Lembre-se de que a ordenação modifica o slice original; se precisar preservar a ordem original, faça uma cópia antes.

Referências

Exercícios

  1. Exercício 1: Escreva uma função que receba um slice de strings e o ordene em ordem alfabética decrescente usando sort.Slice.

    ✓ Resposta: 
    func ordenarDecrescente(s []string) {
    sort.Slice(s, func(i, j int) bool {
        return s[i] > s[j]
    })
}
  2. Exercício 2: Implemente a interface sort.Interface para um tipo Pessoa que ordene por idade de forma crescente e, em caso de empate, por nome.

    ✓ Resposta: 
    type PorIdadeNome []Pessoa

func (p PorIdadeNome) Len() int { return len(p) }
func (p PorIdadeNome) Less(i, j int) bool {
    if p[i].Idade != p[j].Idade {
        return p[i].Idade < p[j].Idade
    }
    return p[i].Nome < p[j].Nome
}
func (p PorIdadeNome) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
  3. Exercício 3: Dado um slice ordenado de inteiros, use sort.SearchInts para encontrar o índice de um valor específico. Se não existir, retorne o índice onde ele deveria ser inserido.

    ✓ Resposta: 
    func buscarIndice(s []int, alvo int) int {
    indice := sort.SearchInts(s, alvo)
    return indice
}
  4. Exercício 4: Explique quando usar sort.SliceStable em vez de sort.Slice e dê um exemplo prático.

    ✓ Resposta: Use sort.SliceStable quando a ordem relativa de elementos iguais for importante. Por exemplo, ao ordenar uma lista de alunos por nota, mas mantendo a ordem alfabética original para notas iguais. 
    sort.SliceStable(alunos, func(i, j int) bool { return alunos[i].Nota < alunos[j].Nota })
  5. Exercício 5: Implemente uma função que, dado um slice de structs com campo Nome e Idade, ordene por idade de forma estável usando sort.SliceStable e depois por nome de forma estável, para garantir que a ordem por idade seja preservada quando os nomes forem iguais.

    ✓ Resposta: 
    func ordenarPessoas(pessoas []Pessoa) {
    // Primeiro por nome (estável)
    sort.SliceStable(pessoas, func(i, j int) bool { return pessoas[i].Nome < pessoas[j].Nome })
    // Depois por idade (estável) – preserva a ordem por nome para idades iguais
    sort.SliceStable(pessoas, func(i, j int) bool { return pessoas[i].Idade < pessoas[j].Idade })
}

Observações finais

A ordenação é uma operação fundamental que aparece em muitos problemas. O pacote sort de Go é poderoso e flexível, permitindo ordenar praticamente qualquer tipo de dado com facilidade. Lembre-se de que a estabilidade pode ser crucial em certos cenários, e a busca binária é uma ferramenta valiosa para consultas rápidas em dados ordenados.

Pratique os conceitos com os exercícios e explore a documentação oficial para mais detalhes. Em projetos reais, você frequentemente encontrará a necessidade de ordenar dados, e dominar essas técnicas fará de você um programador Go mais eficiente.