Bem-vindo à aula sobre ordenação em Go. Ordenar dados é uma das operações mais comuns em programação, e Go oferece um pacote padrão chamado sort que fornece funções eficientes e flexíveis para ordenar fatias e coleções personalizadas. Nesta aula, vamos explorar desde o uso simples de sort.Slice até a implementação da interface sort.Interface, além de entender como realizar buscas em coleções ordenadas e as nuances entre ordenação estável e instável.

Dominar essas ferramentas é essencial para escrever código limpo e eficiente. Vamos começar com a abordagem mais direta: ordenar fatias de qualquer tipo usando uma função de comparação fornecida por você.

sort.Slice

A função sort.Slice é a maneira mais prática de ordenar uma fatia em Go. Ela recebe a fatia e uma função de comparação que define a ordem. A função de comparação deve retornar true se o elemento com índice i deve vir antes do elemento com índice j.

Essa abordagem é ideal quando você não quer (ou não pode) definir um tipo personalizado que implemente a interface sort.Interface. Ela é frequentemente usada com fatias de structs ou tipos primitivos, pois permite uma lógica de comparação arbitrária sem modificar a definição do tipo.

Exemplo: ordenar uma fatia de inteiros em ordem crescente.

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums := []int{5, 2, 6, 3, 1, 4}
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })
    fmt.Println(nums) // [1 2 3 4 5 6]
}

Observe que a função de comparação captura a variável nums e compara os elementos diretamente. Para ordem decrescente, basta inverter o sinal: nums[i] > nums[j].

Um caso comum é ordenar uma fatia de structs por um campo específico. Por exemplo, ordenar uma lista de pessoas por idade:

type Person struct {
    Name string
    Age  int
}

people := []Person{
    {"Alice", 30},
    {"Bob", 20},
    {"Carol", 25},
}

sort.Slice(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})
fmt.Println(people) // [{Bob 20} {Carol 25} {Alice 30}]

Você pode usar qualquer lógica na comparação, inclusive múltiplas condições (por exemplo, ordenar por idade e depois por nome).

Interfaces de ordenação

Para um controle mais fino, Go define a interface sort.Interface, que deve ser implementada por qualquer tipo que queira ser ordenado pelas funções genéricas do pacote sort. A interface exige três métodos: Len(), Less(i, j int) bool e Swap(i, j int).

Implementar essa interface permite que você use funções como sort.Sort e sort.Stable, que são mais flexíveis e eficientes em alguns cenários. Além disso, é a base para personalizar completamente a ordenação de estruturas complexas.

Vamos implementar um tipo PersonSlice que implementa sort.Interface:

type Person struct {
    Name string
    Age  int
}

type PersonSlice []Person

func (ps PersonSlice) Len() int           { return len(ps) }
func (ps PersonSlice) Less(i, j int) bool { return ps[i].Age < ps[j].Age }
func (ps PersonSlice) Swap(i, j int)      { ps[i], ps[j] = ps[j], ps[i] }

func main() {
    people := PersonSlice{
        {"Alice", 30},
        {"Bob", 20},
        {"Carol", 25},
    }
    sort.Sort(people)
    fmt.Println(people) // [{Bob 20} {Carol 25} {Alice 30}]
}

É comum usar fatias nomeadas (como PersonSlice) para adicionar métodos. Você também pode definir métodos diretamente em um tipo []Person se preferir, mas isso não é permitido para tipos definidos em outro pacote.

Uma vantagem de implementar a interface é que você pode usar sort.IsSorted para verificar se uma fatia está ordenada, sem precisar ordená-la de fato.

if sort.IsSorted(people) {
    fmt.Println("Já está ordenado")
}

Além disso, para tipos básicos (como []int e []string), o pacote sort já fornece funções prontas: sort.Ints, sort.Strings, etc.

Busca

O pacote sort também fornece funções de busca eficientes em fatias ordenadas, usando o algoritmo de busca binária. A principal função é sort.Search, que encontra o menor índice onde uma função de comparação retorna true. Para tipos básicos, existem atalhos como sort.SearchInts e sort.SearchStrings.

É crucial que a fatia esteja ordenada antes de usar a busca; caso contrário, o resultado será indefinido. A função sort.Search usa uma função que recebe um índice e retorna um booleano indicando se o elemento naquele índice é maior ou igual ao valor procurado (para busca crescente).

Exemplo: buscar um número em uma fatia de inteiros ordenada.

nums := []int{1, 3, 5, 7, 9}
// A função retorna true se nums[i] >= 5
idx := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= 5
})
if idx < len(nums) && nums[idx] == 5 {
    fmt.Printf("Encontrado no índice %d\n", idx)
} else {
    fmt.Println("Não encontrado")
}

Para tipos básicos, use os atalhos:

idx := sort.SearchInts(nums, 5)

Essas funções retornam o índice onde o valor deveria ser inserido para manter a ordem, mesmo que o valor não exista. Isso é útil para implementar inserção ordenada.

Estável vs instável

Uma ordenação é estável se elementos iguais mantêm sua ordem relativa original. Por exemplo, se você tem uma lista de pessoas com o mesmo nome, uma ordenação estável pela idade preservará a ordem em que elas aparecem na lista original. Ordenações instáveis não garantem isso.

O pacote sort oferece duas funções principais: sort.Sort (que usa um algoritmo instável, geralmente quicksort) e sort.Stable (que garante estabilidade, usando mergesort). A estabilidade pode ser importante quando você ordena por múltiplos critérios: você pode primeiro ordenar por um critério secundário (com uma ordenação estável) e depois por um critério primário, preservando a ordem do critério secundário para elementos iguais.

Exemplo: ordenar uma fatia de structs por nome e depois por idade, mantendo a ordem de nomes iguais.

type Person struct {
    Name string
    Age  int
}

people := []Person{
    {"Alice", 30},
    {"Bob", 20},
    {"Alice", 25},
    {"Carol", 25},
}

// Primeiro ordena por nome (estável)
sort.SliceStable(people, func(i, j int) bool {
    return people[i].Name < people[j].Name
})
// Depois ordena por idade (estável)
sort.SliceStable(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})

fmt.Println(people) // [{Bob 20} {Alice 25} {Alice 30} {Carol 25}]

Note que sort.SliceStable é a versão estável de sort.Slice. Para a interface sort.Interface, use sort.Stable.

Em termos de desempenho, sort.Sort é geralmente mais rápido em média, mas sort.Stable tem complexidade O(n log n) garantida e preserva a ordem para elementos iguais. Escolha a estável quando a ordem relativa for importante; caso contrário, a instável é suficiente.

Boas práticas

  • Para fatias pequenas, a diferença de desempenho entre estável e instável é desprezível; priorize a clareza.
  • Use sort.Slice para casos simples e sort.Interface quando precisar reutilizar a lógica de ordenação em vários lugares ou quando a fatia for de um tipo personalizado.
  • Sempre verifique se a fatia está ordenada antes de usar sort.Search; caso contrário, o resultado é indefinido.
  • Prefira os atalhos sort.Ints, sort.Strings, etc., para tipos básicos, pois são mais legíveis.
  • Quando precisar de múltiplos critérios de ordenação, use sort.SliceStable com ordenações sucessivas, da menos importante para a mais importante.

Referências

Exercícios

  1. Crie uma função que receba uma fatia de inteiros e a ordene em ordem decrescente usando sort.Slice.

    ✓ Resposta: 
    func reverseSort(nums []int) {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] > nums[j]
    })
}

  2. Implemente um tipo StringSlice que implemente sort.Interface para ordenar strings em ordem alfabética (ignorando maiúsculas/minúsculas).

    ✓ Resposta: 
    type StringSlice []string

func (s StringSlice) Len() int { return len(s) }
func (s StringSlice) Less(i, j int) bool {
    return strings.ToLower(s[i]) < strings.ToLower(s[j])
}
func (s StringSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

// Uso:
// sort.Sort(StringSlice([]string{"banana", "Apple", "cherry"}))

  3. Dada uma fatia de inteiros ordenada, escreva uma função que retorne o índice do primeiro elemento maior ou igual a um valor alvo, usando sort.Search.

    ✓ Resposta: 
    func lowerBound(nums []int, target int) int {
    return sort.Search(len(nums), func(i int) bool {
        return nums[i] >= target
    })
}

  4. Explique a diferença entre sort.Sort e sort.Stable e dê um exemplo onde a estabilidade é importante.

    ✓ Resposta:

    sort.Sort usa um algoritmo instável (quicksort), que não garante a ordem relativa de elementos iguais. sort.Stable usa mergesort, garantindo que elementos iguais mantenham sua ordem original. Isso é importante quando você ordena por múltiplos critérios: por exemplo, primeiro por nome e depois por idade, para que pessoas com o mesmo nome fiquem em ordem de idade, preservando a ordem original do nome.

  5. Crie uma fatia de structs Produto com campos Nome e Preço e a ordene por preço de forma estável. Depois, ordene por nome de forma estável e mostre o resultado.

    ✓ Resposta: 
    type Produto struct {
    Nome  string
    Preco float64
}

produtos := []Produto{
    {"Notebook", 3000},
    {"Mouse", 50},
    {"Teclado", 100},
    {"Notebook", 2500},
}

// Ordena por preço (estável)
sort.SliceStable(produtos, func(i, j int) bool {
    return produtos[i].Preco < produtos[j].Preco
})
fmt.Println(produtos) // [{Mouse 50} {Teclado 100} {Notebook 2500} {Notebook 3000}]

// Ordena por nome (estável) - mantém a ordem por preço para nomes iguais
sort.SliceStable(produtos, func(i, j int) bool {
    return produtos[i].Nome < produtos[j].Nome
})
fmt.Println(produtos) // [{Mouse 50} {Notebook 2500} {Notebook 3000} {Teclado 100}]