[391] qsort e bsearch: Ordenando e Buscando com a Biblioteca

Na aula anterior, aprendemos a passar comportamento como argumento através de ponteiros para função. Hoje colhemos o fruto mais imediato dessa ideia. A biblioteca padrão do C oferece duas funções poderosas — qsort, que ordena, e bsearch, que busca — capazes de trabalhar com qualquer tipo de dado. E o segredo de como elas conseguem essa generalidade é exatamente o ponteiro para função: você fornece o critério de comparação, e elas cuidam do algoritmo. Ao dominá-las, você evita reescrever ordenação a cada projeto e entende um padrão de design que atravessa toda a programação.

O problema da ordenação genérica

Ordenar um vetor de inteiros é simples. Mas e ordenar structs por um campo? E strings em ordem alfabética? E números em ordem decrescente? Se cada caso exigisse um algoritmo de ordenação próprio, seria um trabalho repetitivo e propenso a erros. A biblioteca resolve isso com uma abordagem elegante: qsort implementa o algoritmo de ordenação uma vez, de forma genérica, e delega a você apenas a decisão de como comparar dois elementos. Essa separação — algoritmo genérico, critério específico — é a razão de sua flexibilidade.

A assinatura de qsort

A função qsort, de <stdlib.h>, recebe quatro argumentos:

void qsort(void *base, size_t n, size_t tamanho,
           int (*comparar)(const void *, const void *));

Decifrando cada um: base é o endereço do vetor (por que void *, veremos já já); n é o número de elementos; tamanho é o tamanho de cada elemento em bytes (via sizeof); e comparar é um ponteiro para função — o callback que diz como ordenar. O tipo de retorno e os parâmetros de qsort usam void *, o "ponteiro genérico" do C, que pode apontar para qualquer tipo. É esse void * que permite a qsort trabalhar com inteiros, structs ou o que for — ela não precisa saber o tipo, só o tamanho e como comparar.

A função de comparação: o coração de tudo

O callback de comparação segue um contrato preciso, herdado da matemática da ordenação. Ele recebe ponteiros para dois elementos e deve retornar: um número negativo se o primeiro vem antes do segundo, zero se são equivalentes, e positivo se o primeiro vem depois. Vamos ordenar um vetor de inteiros:

#include <stdio.h>
#include <stdlib.h>

// compara dois inteiros para ordem crescente
int comparar_int(const void *a, const void *b) {
    int x = *(const int *)a; // converte void* para int* e desreferencia
    int y = *(const int *)b;
    return x - y; // negativo, zero ou positivo
}

int main(void) {
    int v[] = {42, 7, 13, 99, 1, 27};
    int n = sizeof(v) / sizeof(v[0]);

    qsort(v, n, sizeof(int), comparar_int);

    for (int i = 0; i < n; i++) printf("%d ", v[i]); // 1 7 13 27 42 99
    printf("\n");
    return 0;
}

A parte que exige atenção é o corpo de comparar_int. Ela recebe const void *a e const void *b — ponteiros genéricos. Para usá-los como inteiros, primeiro os convertemos para const int * (com o cast (const int *)a) e depois desreferenciamos (*), obtendo os valores. O return x - y explora o contrato de forma esperta: se x < y, a diferença é negativa; se iguais, zero; se x > y, positiva — exatamente o que qsort espera. Toda a magia de ordenar está terceirizada; você só disse como comparar.

Um cuidado com o "x - y"

O truque x - y é conciso, mas tem uma armadilha que vale conhecer: para inteiros muito grandes, a subtração pode estourar (overflow) e produzir um sinal errado. A forma robusta usa comparações explícitas:

int comparar_int_seguro(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    if (x < y) return -1;
    if (x > y) return  1;
    return 0;
}

Para valores pequenos, x - y funciona bem e é comum em exemplos; para código de produção com inteiros que podem ser grandes, prefira as comparações explícitas. É a mesma disciplina defensiva que o C sempre pede: pensar nos casos extremos.

Ordenando em ordem decrescente ou por outros critérios

A beleza do design fica evidente quando mudamos o critério sem tocar no algoritmo. Para ordem decrescente, basta inverter a comparação:

int comparar_desc(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return y - x; // invertido: agora ordena do maior para o menor
}

Trocar x - y por y - x inverte toda a ordenação. Uma mesma qsort, comportamentos opostos, apenas pela escolha do callback — a demonstração viva do poder dos ponteiros para função da aula anterior.

Ordenando structs por um campo

Aqui o valor de qsort explode: ordenar um vetor de structs por qualquer campo é trivial. Vamos ordenar pessoas por idade:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nome[50];
    int idade;
} Pessoa;

// compara duas pessoas pela idade
int comparar_por_idade(const void *a, const void *b) {
    const Pessoa *p1 = (const Pessoa *)a;
    const Pessoa *p2 = (const Pessoa *)b;
    return p1->idade - p2->idade;
}

int main(void) {
    Pessoa turma[] = {
        {"Ana", 30}, {"Bruno", 25}, {"Carla", 35}, {"Diego", 28}
    };
    int n = sizeof(turma) / sizeof(turma[0]);

    qsort(turma, n, sizeof(Pessoa), comparar_por_idade);

    for (int i = 0; i < n; i++) {
        printf("%s: %d anos\n", turma[i].nome, turma[i].idade);
    }
    // Bruno: 25, Diego: 28, Ana: 30, Carla: 35
    return 0;
}

O callback converte os void * para const Pessoa * e compara pelo campo idade. Para ordenar por nome em vez de idade, você escreveria outro callback usando strcmp(p1->nome, p2->nome) — e note que strcmp já segue o mesmo contrato (negativo/zero/positivo), encaixando-se perfeitamente. Trocar o critério de ordenação é trocar o callback; o vetor, o tamanho e a qsort permanecem idênticos.

bsearch: busca binária pronta

A companheira de qsort é bsearch, que faz uma busca binária — localiza um elemento num vetor já ordenado com enorme eficiência (examinando o meio e descartando metade a cada passo). Sua assinatura é quase idêntica à de qsort, mais o elemento procurado:

#include <stdio.h>
#include <stdlib.h>

int comparar_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

int main(void) {
    int v[] = {1, 7, 13, 27, 42, 99}; // JÁ ORDENADO — pré-requisito!
    int n = sizeof(v) / sizeof(v[0]);

    int chave = 27;
    int *achado = bsearch(&chave, v, n, sizeof(int), comparar_int);

    if (achado != NULL) {
        printf("Encontrado %d na posição %ld\n", *achado, achado - v); // posição 3
    } else {
        printf("Não encontrado.\n");
    }
    return 0;
}

O bsearch devolve um ponteiro para o elemento encontrado (ou NULL). Repare que ele reutiliza a mesma função de comparação de qsort — as duas foram feitas para trabalhar juntas. Mas há um pré-requisito absoluto: o vetor precisa estar ordenado para bsearch funcionar; a busca binária depende disso. O fluxo idiomático é: ordene uma vez com qsort, depois busque muitas vezes com bsearch. A eficiência compensa enormemente em vetores grandes: uma busca linear examinaria, no pior caso, todos os elementos; a binária examina apenas o logaritmo desse número.

Por que aprender isso importa além da conveniência

Poderíamos escrever nossa própria ordenação — e faremos, nas aulas de estruturas de dados, para entender os algoritmos por dentro. Mas há três razões para usar qsort/bsearch no dia a dia: elas são testadas e otimizadas (mais confiáveis que uma versão caseira às pressas), genéricas (um único código serve a qualquer tipo), e idiomáticas (todo programador C as reconhece). Mais do que isso, elas ensinam um padrão de design fundamental — o algoritmo genérico parametrizado por um callback — que você reencontrará em incontáveis contextos. Compreender por que elas usam void * e ponteiros para função é compreender como o C, apesar de não ter recursos de linguagens modernas, alcança generalidade.

Fechando a Fase 4

Com esta aula, encerramos a fase de entrada, saída e biblioteca padrão. Você aprendeu a fazer o programa conversar com o usuário e com arquivos (texto e binário), a aproveitar a rica biblioteca padrão, a manipular texto com segurança, e a usar ponteiros para função para escrever código genérico — culminando em qsort e bsearch. Na próxima fase, viramos uma chave importante: em vez de usar algoritmos e estruturas prontos, vamos construí-los do zero. Começamos pela recursão, a técnica em que uma função chama a si mesma — elegante, poderosa, e a base natural para percorrer as estruturas encadeadas que dominarão a Fase 5.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 5.11, sobre qsort e ponteiros para função
• cppreference — qsort — https://en.cppreference.com/w/c/algorithm/qsort
• cppreference — bsearch — https://en.cppreference.com/w/c/algorithm/bsearch
• Modern C, Jens Gustedt — seção sobre algoritmos genéricos com void * — https://gustedt.gitlabpages.inria.fr/modern-c/
• CERT C — sobre uso correto de void * e funções de comparação — https://wiki.sei.cmu.edu/confluence/display/c

Exercícios

Exercício 1

Use qsort para ordenar um vetor de 8 inteiros em ordem crescente. Depois, escreva um segundo callback e ordene o mesmo vetor em ordem decrescente. Imprima ambos os resultados.

#include <stdio.h>
#include <stdlib.h>

int crescente(const void *a, const void *b) {
    return (*(const int *)a > *(const int *)b) - (*(const int *)a < *(const int *)b);
}
int decrescente(const void *a, const void *b) {
    return crescente(b, a); // inverte os argumentos
}

int main(void) {
    int v[8] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;

    qsort(v, n, sizeof(int), crescente);
    for (int i = 0; i < n; i++) printf("%d ", v[i]); // 1 2 3 4 5 7 8 9
    printf("\n");

    qsort(v, n, sizeof(int), decrescente);
    for (int i = 0; i < n; i++) printf("%d ", v[i]); // 9 8 7 5 4 3 2 1
    printf("\n");
    return 0;
}

Exercício 2

Defina uma struct Produto (com nome e preco) e um vetor com 4 produtos. Use qsort para ordená-los por preço (do mais barato ao mais caro) e imprima o resultado.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { char nome[40]; double preco; } Produto;

int por_preco(const void *a, const void *b) {
    double pa = ((const Produto *)a)->preco;
    double pb = ((const Produto *)b)->preco;
    if (pa < pb) return -1;
    if (pa > pb) return  1;
    return 0;
}

int main(void) {
    Produto v[4] = {{"Mochila", 149.9}, {"Caneta", 2.5}, {"Caderno", 12.9}, {"Estojo", 25.0}};
    qsort(v, 4, sizeof(Produto), por_preco);
    for (int i = 0; i < 4; i++) printf("%s: R$ %.2f\n", v[i].nome, v[i].preco);
    return 0;
}

Exercício 3

Escreva um callback que ordene um vetor de strings (char *nomes[]) em ordem alfabética, usando strcmp dentro dele. (Dica: os elementos são char *, então o callback recebe ponteiros para char *, exigindo um cast para char ** e uma desreferência.)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int alfabetico(const void *a, const void *b) {
    // cada elemento é um char*, então recebemos ponteiros para char*
    const char *s1 = *(const char **)a;
    const char *s2 = *(const char **)b;
    return strcmp(s1, s2);
}

int main(void) {
    const char *nomes[] = {"Carla", "Ana", "Diego", "Bruno"};
    int n = 4;
    qsort(nomes, n, sizeof(char *), alfabetico);
    for (int i = 0; i < n; i++) printf("%s ", nomes[i]); // Ana Bruno Carla Diego
    printf("\n");
    return 0;
}

Exercício 4

Ordene um vetor de inteiros com qsort e, em seguida, use bsearch para procurar três valores: um que existe, um que não existe, e o menor do vetor. Imprima o resultado de cada busca.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(const int*)a > *(const int*)b) - (*(const int*)a < *(const int*)b);
}

int main(void) {
    int v[] = {42, 7, 13, 99, 1, 27};
    int n = 6;
    qsort(v, n, sizeof(int), cmp); // ordena primeiro: 1 7 13 27 42 99

    int chaves[] = {27, 50, 1};
    for (int i = 0; i < 3; i++) {
        int *r = bsearch(&chaves[i], v, n, sizeof(int), cmp);
        if (r != NULL) printf("%d encontrado (pos %ld)\n", chaves[i], r - v);
        else           printf("%d não encontrado\n", chaves[i]);
    }
    return 0;
}

Exercício 5

Explique por que a função de comparação de qsort recebe parâmetros do tipo const void * em vez de, por exemplo, const int *. Como isso se relaciona com a capacidade de qsort ordenar qualquer tipo de dado?