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:
- base: Ponteiro para o primeiro elemento do array a ser ordenado
- num: Número de elementos no array
- size: Tamanho em bytes de cada elemento
- 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:
- palavra - ponteiro para o primeiro caractere da string
- strlen(palavra) - número de caracteres a ordenar (4)
- sizeof(char) - tamanho de cada elemento (1 byte)
- 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
(a vem antes)
- Zero se a == b (iguais)
- Positivo se
(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.
void qsort(void *base, size_t num, size_t size, int (*comparador)(const void*, const void*
// 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"
int compara_char(const void *a, const void *b) {
return (*(char*)a - *(char*)b);
}
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}
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"}
int compara_decrescente(const void *a, const void *b) {
return (*(int*)b - *(int*)a); // Inverte a subtração
}
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:
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 *, oqsorttrata os elementos como blocos de bytes genéricos. Na prática você passa o nome do array (ex.:numerosoupalavra).num: número de elementos a ordenar. Se for uma string e você quer ordenar só os caracteres (sem o'\0'), passestrlen(palavra).size: tamanho em bytes de cada elemento. Ex.:sizeof(char),sizeof(int),sizeof(char*),sizeof(MinhaStruct).comparador: ponteiro para função com assinaturaint compar(const void *a, const void *b). Oqsortvai chamar essa função para comparar dois elementos quaisquer; ela deve dizer sea < b,a == boua > 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:
const void *aeconst void *bsão ponteiros genéricos. Oqsortpassa o endereço do elemento A e do elemento B (cada um é um bloco desizebytes).(char*)aconverte o ponteiro genérico parachar *. Isso é necessário porque vamos tratar cada elemento comochar.*(char*)adesreferencia o ponteiro convertido e obtém o valor do caractere.- A expressão
*(char*)a - *(char*)bproduz:- negativo se o caractere
avem antes deb; - zero se iguais;
- positivo se
avem depois deb.
- negativo se o caractere
- Assim, a função tem exatamente o comportamento que o
qsortespera.
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:
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 abase.strlen(palavra)é o número de caracteres sem contar'\0'(aqui4), então apenas os 4 letras serão ordenadas. Se você passassestrlen(palavra)+1incluiria 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
qsortsó exige sinal negativo/zero/positivo; não precisa ser exatamente a diferença numérica.
Passo 6
Ordenar array de strings (
Código:
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 tipochar *(ponteiro para string). - Quando
qsortpassaconst void *a, esse ponteiro aponta para um elemento do array — ou seja, para umchar *. - Assim,
adeve ser convertido paraconst char * const *(ponteiro para ponteiro parachar) e então desreferenciado*papara obter ochar *efetivo que aponta para a string. strcmpcompara 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
aebparaconst Pessoa *obtemos o endereço do elemento do array (cada elemento é umPessoa). - Acessamos o campo
idadecom->. - Ordenando por
idadeproduz 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:
qsortda biblioteca padrão C não garante ordenação estável. Se precisar preservar ordem relativa de elementos iguais,qsortpode não servir. - Complexidade: tempo médio
; pior caso dependendo da implementação e dos dados. - Alocação e alinhamento:
qsorttroca blocos desizebytes; certifique-se quesizeé o certo para o tipo (usarsizeof(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 queaebno comparador são ponteiros para os elementos (ou seja, ponteiros para ponteiros).
Passo 10
Exemplo completo e comentado — ordenar inteiros (programa pequeno):
Código:
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:
né calculado corretamente comsizeof(numeros)/sizeof(numeros[0]).qsortrecebe o endereço do primeiro elemento (numeros), a quantidaden, o tamanho do elementosizeof(numeros[0])e o comparador.qsortchamacompara_intvárias vezes; cada chamada converte osconst void *recebidos paraconst int *e compara os valores.- 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)comsize = sizeof(tipo)enum= número de elementos. - O comparador tem assinatura
int f(const void *a, const void *b); convertaa/bpara 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), convertaa/bparaconst char * const *e chamestrcmp(*pa, *pb). qsorté in-place e não é estável; complexidade média.