qsort

A função qsort é uma função da biblioteca stdlib.h que implementa um algoritmo de ordenação rápida (Quick Sort) para ordenar arrays de qualquer tipo de dado.
Protótipo:
void qsort(void *base, size_t num, size_t size, int (*comparador)(const void*, const void*

Parâmetros:

  1. base: Ponteiro para o primeiro elemento do array a ser ordenado
  2. num: Número de elementos no array
  3. size: Tamanho em bytes de cada elemento
  4. comparador: Ponteiro para uma função de comparação que determina a ordem

Retorno:

  • A função não retorna valor (void), mas modifica o array original ordenando-o

Como funciona

A qsort precisa de uma função de comparação que você deve criar. Essa função recebe dois ponteiros (para dois elementos a serem comparados) e deve retornar:
  • Valor negativo (< 0): se o primeiro elemento deve vir antes do segundo
  • Zero (0): se os elementos são iguais
  • Valor positivo (> 0): se o primeiro elemento deve vir depois do segundo
Exemplo no código da atividade
// Função de comparação para caracteres
int compara_char(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}
// Usando qsort para ordenar uma string
char palavra[20] = "roma";
qsort(palavra, strlen(palavra), sizeof(char), compara_char);
// Resultado: palavra agora contém "amor"
Explicação passo a passo:
  1. palavra - ponteiro para o primeiro caractere da string
  2. strlen(palavra) - número de caracteres a ordenar (4)
  3. sizeof(char) - tamanho de cada elemento (1 byte)
  4. compara_char - função que compara dois caracteres
A Função de Comparação
int compara_char(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}
O que acontece:
  • const void *a e const void *b são ponteiros genéricos
  • (char*)a converte o ponteiro void para ponteiro de char
  • (char)a obtém o valor do caractere apontado
  • A subtração retorna:
  • Negativo se \mathbf{a}<\mathbf{b} (a vem antes)
  • Zero se a == b (iguais)
  • Positivo se \mathbf{a}>\mathbf{b} (a vem depois)

Outros Exemplos Práticos

Ordenar array de inteiros:
int compara_int(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int numeros[] = {5, 2, 8, 1, 9};
qsort(numeros, 5, sizeof(int), compara_int);
// Resultado: {1, 2, 5, 8, 9}
Ordenar array de strings:
int compara_string(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}
char *nomes[] = {"Maria", "Ana", "Carlos"};
qsort(nomes, 3, sizeof(char*), compara_string);
// Resultado: {"Ana", "Carlos", "Maria"}
Ordenar em ordem decrescente:
int compara_decrescente(const void *a, const void *b) {
    return (*(int*)b - *(int*)a); // Inverte a subtração
}
Por que usar no detector de anagramas?
No exercício, usamos qsort para ordenar os caracteres de cada palavra. Se duas palavras são anagramas, após ordenar seus caracteres, elas ficam idênticas:
  • "amor"→ ordenado → “amor”
  • "roma"→ ordenado → “amor”
  • Como ficaram iguais após ordenação, são anagramas!
Essa é uma técnica eficiente para detectar anagramas sem precisar contar cada letra manualmente.

Passo 1

O que você me enviou e o que eu vou fazer por você agora: você trouxe a explicação básica do qsort (protótipo, parâmetros e exemplos). Vou transformar isso numa aula prática e passo a passo, mostrando exatamente como usar qsort, explicar cada peça (o que é void *base, size, o comparador, como funcionam casts e desreferências) e ainda apontar armadilhas comuns e exemplos concretos (chars, ints, strings, structs, ordem decrescente). Vou também mostrar comparadores seguros e um exemplo completo de programa. Tudo mastigado, sem pular etapas.
Informações relevantes dadas (resumidas):
  • Protótipo: void qsort(void *base, size_t num, size_t size, int (*comparador)(const void*, const void*));
  • O comparador recebe dois const void * e deve retornar negativo/zero/positivo conforme a ordem.
  • Exemplos fornecidos: ordenar caracteres de uma string, inteiros, vetor de char * (strings), ordem decrescente invertendo a subtração.

Passo 2

Entendendo os parâmetros do qsort — cada um explicado bem devagar:
  • base: é um ponteiro para o primeiro elemento do array. Como é void *, o qsort trata os elementos como blocos de bytes genéricos. Na prática você passa o nome do array (ex.: numeros ou palavra).
  • num: número de elementos a ordenar. Se for uma string e você quer ordenar só os caracteres (sem o '\0'), passe strlen(palavra).
  • size: tamanho em bytes de cada elemento. Ex.: sizeof(char), sizeof(int), sizeof(char*), sizeof(MinhaStruct).
  • comparador: ponteiro para função com assinatura int compar(const void *a, const void *b). O qsort vai chamar essa função para comparar dois elementos quaisquer; ela deve dizer se a < b, a == b ou a > b.
Por que qsort pega void * e size? Porque qsort opera em memória bruta: ele copia e troca blocos de size bytes. Ele não sabe o tipo por si só — você informa isso com size e com o comparador.

Passo 3

Como escrever o comparador — conceito e anatomia (linha a linha). Vou usar o exemplo de caractere mostrado por você:
Código:
int compara_char(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}
Explicando devagar:
  1. const void *a e const void *b são ponteiros genéricos. O qsort passa o endereço do elemento A e do elemento B (cada um é um bloco de size bytes).
  2. (char*)a converte o ponteiro genérico para char *. Isso é necessário porque vamos tratar cada elemento como char.
  3. *(char*)a desreferencia o ponteiro convertido e obtém o valor do caractere.
  4. A expressão *(char*)a - *(char*)b produz:
    • negativo se o caractere a vem antes de b;
    • zero se iguais;
    • positivo se a vem depois de b.
  5. Assim, a função tem exatamente o comportamento que o qsort espera.
Observação importante sobre este exemplo: para char (tamanho pequeno) essa diferença funciona bem. Para tipos inteiros maiores esse método pode causar overflow — vamos ver solução segura no próximo passo.

Passo 4

Exemplo prático: ordenar os caracteres de uma string (detalhes importantes)
Código de uso:
char palavra[] = "roma";
qsort(palavra, strlen(palavra), sizeof(char), compara_char);
Explicação das escolhas:
  • palavra (sem &) é o ponteiro para o primeiro caractere -> corresponde a base.
  • strlen(palavra) é o número de caracteres sem contar '\0' (aqui 4), então apenas os 4 letras serão ordenadas. Se você passasse strlen(palavra)+1 incluiria o '\0', o que normalmente não faz sentido.
  • sizeof(char) é 1 — cada elemento tem 1 byte.
  • compara_char é a função que descrevemos.
Depois do qsort, o conteúdo de palavra vira "amor" (os caracteres reordenados). Lembrete: qsort modifica o array in-place.

Passo 5

Comparador para int — problema clássico do overflow e solução segura.
Comparador perigoso (não recomendado):
int compara_int_perigoso(const void *a, const void *b) {
    return (*(int*)a - *(int*)b); // pode overflow!
}
Por que é perigoso? Se *(int*)a for muito grande positivo e *(int*)b muito negativo, a subtração pode ultrapassar o intervalo de int e provocar comportamento indefinido.
Comparador seguro (recomendado):
int compara_int(const void *a, const void *b) {
    int va = *(const int*)a;
    int vb = *(const int*)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}
Ou, mais compacto e equivalente em C99:
int compara_int2(const void *a, const void *b) {
    int va = *(const int*)a;
    int vb = *(const int*)b;
    return (va > vb) - (va < vb); // resulta em 1,0 ou -1
}
Explicação da versão segura:
  • Faz-se a comparação lógica em vez da subtração para evitar overflow.
  • O qsort só exige sinal negativo/zero/positivo; não precisa ser exatamente a diferença numérica.

Passo 6

Ordenar array de strings (char *nomes[]) — por que o comparador usa char * const *:
Código:
int compara_string(const void *a, const void *b) {
    const char * const *pa = a;
    const char * const *pb = b;
    return strcmp(*pa, *pb);
}
Explicando:
  • Cada elemento do array nomes é do tipo char * (ponteiro para string).
  • Quando qsort passa const void *a, esse ponteiro aponta para um elemento do array — ou seja, para um char *.
  • Assim, a deve ser convertido para const char * const * (ponteiro para ponteiro para char) e então desreferenciado *pa para obter o char * efetivo que aponta para a string.
  • strcmp compara as strings lexicograficamente e retorna negativo/zero/positivo conforme necessário.
Uso:
char *nomes[] = {"Maria", "Ana", "Carlos"};
qsort(nomes, 3, sizeof(char*), compara_string);
// nomes = {"Ana", "Carlos", "Maria"}
Dica: em qsort de ponteiros sempre use sizeof(char*) (tamanho do ponteiro).

Passo 7

Ordenando arrays de structs — exemplo completo e explicação passo a passo.
Exemplo de struct e comparador por idade:
typedef struct {
    char nome[50];
    int idade;
} Pessoa;

int compara_por_idade(const void *a, const void *b) {
    const Pessoa *pa = a;
    const Pessoa *pb = b;
    if (pa->idade < pb->idade) return -1;
    if (pa->idade > pb->idade) return 1;
    return 0;
}
Uso:
Pessoa v[] = { {"Joao", 30}, {"Ana", 25}, {"Carlos", 28} };
qsort(v, 3, sizeof(Pessoa), compara_por_idade);
Explicando:
  • Convertendo a e b para const Pessoa * obtemos o endereço do elemento do array (cada elemento é um Pessoa).
  • Acessamos o campo idade com ->.
  • Ordenando por idade produz array em ordem crescente de idade.
Para ordenar por nome em ordem alfabética, troque a comparação por strcmp(pa->nome, pb->nome).

Passo 8

Ordenação decrescente e pequenas variantes
  • Para inverter a ordem, basta inverter o sinal do comparador.
    Exemplo com inteiros:
int compara_decrescente(const void *a, const void *b) {
    int va = *(const int*)a;
    int vb = *(const int*)b;
    if (va < vb) return 1;
    if (va > vb) return -1;
    return 0;
}
Ou reaproveitar o comparador crescente:
int compara_decrescente2(const void *a, const void *b) {
    return -compara_int(a, b); // cuidado se comparador não retornar apenas -1,0,1 (mas normalmente ok)
}
Observação: inverter o sinal de um comparador que retorna grandes diferenças numéricas pode causar overflow; prefira inverter sinais lógicos como nos exemplos acima.

Passo 9

Regras importantes, desempenho e armadilhas — anote estas na prova:
  • Consistência do comparador: a função deve definir uma ordem estrita e consistente (transitiva). Se o comparador não for coerente, o comportamento do qsort é indefinido (pode ficar em loop ou produzir resultado inválido).
  • Retorno: apenas a sinalização negativa/zero/positiva importa; não é obrigatório retornar -1/0/1, mas é seguro e claro.
  • Estabilidade: qsort da biblioteca padrão C não garante ordenação estável. Se precisar preservar ordem relativa de elementos iguais, qsort pode não servir.
  • Complexidade: tempo médio \mathcal{O}(n\log n); pior caso \mathcal{O}(n^2) dependendo da implementação e dos dados.
  • Alocação e alinhamento: qsort troca blocos de size bytes; certifique-se que size é o certo para o tipo (usar sizeof(tipo) evita erro).
  • Não chame funções que mudam os elementos dentro do comparador de formas inesperadas (ex.: mudar campos dos elementos), porque o comparador deve ser puro (apenas comparar).
  • Pointer-to-pointer: quando elementos são ponteiros (ex.: char *v[]), lembre-se que a e b no comparador são ponteiros para os elementos (ou seja, ponteiros para ponteiros).

Passo 10

Exemplo completo e comentado — ordenar inteiros (programa pequeno):
Código:
#include <stdio.h>
#include <stdlib.h>

int compara_int(const void *a, const void *b) {
    int va = *(const int*)a;
    int vb = *(const int*)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}

int main(void) {
    int numeros[] = {5, 2, 8, 1, 9};
    size_t n = sizeof(numeros) / sizeof(numeros[0]);
    qsort(numeros, n, sizeof(numeros[0]), compara_int);
    for (size_t i = 0; i < n; ++i) {
        printf("%d ", numeros[i]);
    }
    printf("\n");
    return 0;
}
Passo a passo do que acontece:
  1. n é calculado corretamente com sizeof(numeros)/sizeof(numeros[0]).
  2. qsort recebe o endereço do primeiro elemento (numeros), a quantidade n, o tamanho do elemento sizeof(numeros[0]) e o comparador.
  3. qsort chama compara_int várias vezes; cada chamada converte os const void * recebidos para const int * e compara os valores.
  4. O array numeros é modificado in-place e impresso ordenado: 1 2 5 8 9.

Resposta

Resumo prático e pontos essenciais que você deve lembrar para a prova:
  • Use qsort(base, num, size, compar) com size = sizeof(tipo) e num = número de elementos.
  • O comparador tem assinatura int f(const void *a, const void *b); converta a/b para o tipo correto e compare, retornando negativo/zero/positivo.
  • Para inteiros, evite return (*(int*)a - *(int*)b); por risco de overflow; use comparações lógicas.
  • Para char * (array de strings), converta a/b para const char * const * e chame strcmp(*pa, *pb).
  • qsort é in-place e não é estável; complexidade média \mathcal{O}(n\log n).

Exercícios relacionados