Quicksort
Divisão e conquista.
Quicksort é uma aula grátis de C Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
Divisão e conquista
Quicksort é um algoritmo de ordenação por divisão e conquista. Ele escolhe um pivô, particiona o vetor para que os elementos menores fiquem à esquerda e os maiores à direita e, em seguida, ordena recursivamente cada lado.
O tempo médio é O(n log n).
A etapa de particionamento
A ideia principal é o particionamento: reorganizar o vetor ao redor de um pivô, de modo que tudo à esquerda do pivô seja menor e tudo à direita seja maior. O pivô então fica em sua posição final ordenada.
Esquema de particionamento de Lomuto
O esquema de Lomuto usa o último elemento como pivô. Ele mantém um índice i para o limite dos elementos menores e realiza trocas enquanto percorre o vetor.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}A ordenação recursiva
O quicksort chama o particionamento e depois faz chamadas recursivas para os dois subvetores ao redor do pivô. O caso-base é um subvetor de tamanho 0 ou 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Escolhendo um bom pivô
Um pivô ruim (como escolher sempre o último elemento em uma entrada ordenada) causa comportamento O(n ao quadrado). Escolhas melhores distribuem as partições de maneira mais uniforme.
- Mediana de três
- Pivô aleatório
Mediana de três
A mediana de três escolhe como pivô a mediana do primeiro, do elemento central e do último elemento, evitando o pior caso em dados já ordenados.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Análise do pior caso
Se cada partição separar apenas um elemento, a profundidade da recursão chegará a n e o custo será O(n ao quadrado). Isso acontece com um pivô fixo em entradas ordenadas ou ordenadas ao contrário.
A aleatorização torna o pior caso extremamente improvável.
Pivô aleatório
Trocar um elemento aleatório para a posição do pivô antes do particionamento protege contra entradas adversárias.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}No próprio vetor e não estável
O quicksort ordena no próprio vetor, usando em média apenas O(log n) de espaço na pilha. No entanto, ele não é estável: elementos iguais podem mudar de ordem devido às trocas no particionamento.
Otimização de chamada final
Fazer a chamada recursiva primeiro para a metade menor e usar um laço para a metade maior limita a profundidade da pilha a O(log n), evitando estouro de pilha em vetores grandes.
Ordenando cadeias de caracteres
A mesma estrutura ordena qualquer tipo comparável. Aqui, o quicksort ordena um vetor de inteiros, mas trocar a comparação também permite ordenar outros tipos.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Verificação rápida
Teste sua compreensão sobre quicksort.
Recapitulação
Você aprendeu quicksort.
- Particione ao redor de um pivô e depois faça chamadas recursivas para cada lado
- O caso médio é O(n log n), e o pior caso é O(n ao quadrado)
- Pivôs por mediana de três ou aleatórios evitam o pior caso
- Ordena no próprio vetor, mas não é estável
Perguntas Frequentes
A aula “Quicksort” é grátis?
Sim — o texto completo de “Quicksort” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Quicksort”?
Divisão e conquista. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Quicksort”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.