Bubble, selection e insertion sort em C, visualizados passo a passo.
📖 O que você vai aprender nesta página
✅ O essencial para saber
Bubble sort: troca pares adjacentes
Selection sort: puxa o mínimo para o início
O qsort da biblioteca padrão
⭐ Leia se tiver tempo
Quicksort, mergesort
Complexidade: O(n²) vs O(n log n)
Ordenação estável vs instável
O que é Ordenação? — Reorganizando Dados em Ordem
Reorganizar elementos de um array em ordem crescente ou decrescente é chamado de ordenação. É um bloco fundamental para buscas rápidas e para organizar dados.
Algoritmos de ordenação comuns
Algoritmo
Complexidade média
Característica
Bubble sort
O(n²)
O mais simples; compara e troca itens adjacentes
Selection sort
O(n²)
Acha o mínimo e coloca no começo
Insertion sort
O(n²)
Como ordenar cartas na mão; rápido em dados quase ordenados
Quicksort
O(n log n)
O mais rápido na prática; o qsort() do C é baseado nele
Iniciantes devem começar com bubble → selection → insertion. Os três usam laços aninhados — ótima prática para reforçar os fundamentos do for.
Bubble Sort — Compare e Troque Elementos Adjacentes
Compara elementos adjacentes e os troca se estiverem na ordem errada. Repetir esse processo faz os maiores valores "borbulharem" até o final.
voidbubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j+1]) {
// trocaint tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
A ordenação mais simples de implementar — ótima para aprender.
Selection Sort — Ache o Mínimo, Coloque no Começo
Da parte não ordenada, ache o mínimo e troque-o para o primeiro slot não ordenado. Repita até tudo ficar no lugar.
voidselectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx])
minIdx = j; // acompanha o índice do mínimo
}
// troca a posição i com o mínimoint tmp = a[i];
a[i] = a[minIdx];
a[minIdx] = tmp;
}
}
Movimento mínimo de elementos; muito claro conceitualmente.
Insertion Sort — Ordenando Cartas na Sua Mão
Considere a parte esquerda como já ordenada. Para cada elemento restante, insira no lugar certo. Pense em arrumar as cartas enquanto as pega.
voidinsertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i]; // valor a inserirint j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j]; // desloca para a direita
j--;
}
a[j+1] = key; // coloca no ponto correto
}
}
Como ele avança
[5| 3 8 1 4] → inserir 3 → [3 5| 8 1 4]
[3 5| 8 1 4] → 8 permanece → [3 5 8| 1 4]
[3 5 8| 1 4] → 1 vai para o começo → [1 3 5 8| 4]
[1 3 5 8| 4] → 4 entre 3 e 5 → [1 3 4 5 8] Pronto!
Tudo à esquerda do | já está ordenado.
Complexidade
O(n²) no pior caso, O(n) em dados quase ordenados (bem rápido)
Vantagem
Ótimo para entradas pequenas ou quase ordenadas. Também é estável.
Visualizador de Ordenação
Escolha um algoritmo e clique em Iniciar para ver o array sendo ordenado, passo a passo.
Clique em Iniciar para começar a animação.
Comparações: 0Trocas: 0
🎯 Busca Linear vs Binária — Visualize a diferença de eficiência
Ao buscar em um array ordenado, a busca linear percorre do começo um elemento de cada vez, enquanto a busca binária divide o intervalo pela metade a cada passo. Execute as duas lado a lado e veja por si a diferença no número de comparações.
📏 Busca linear (um por um desde o início)
Comparações: 0
Status: -
🎯 Busca binária (compara o meio, divide o intervalo)
Comparações: 0
Intervalo [low, high]: -
Status: -
Encontre um valor num array ordenado. Mude o "Alvo" e execute.
N
Linear (pior)
Binária (pior)
Proporção
10
10
4
2,5×
100
100
7
14×
1.000
1.000
10
100×
1.000.000
1.000.000
20
50.000×
💡 Pré-requisito: a busca binária exige um array ordenado. Ordenar custa O(n log n), então para uma única busca, a linear é mais barata no total. Mas para buscas repetidas no mesmo array, a binária vence por uma margem gigante. O(log n) é uma classe de complexidade fundamental — árvores binárias, heaps e muitas outras estruturas compartilham dela.
P. Qual algoritmo de ordenação é o mais rápido no geral?
R. Na prática, o Quicksort é o mais rápido para a maioria das cargas. Sua complexidade média de tempo é O(n log n) e as implementações são bem eficientes. Dependendo dos dados, o merge sort ou o heap sort podem sair na frente. Código de produção escolhe o que melhor se encaixa na situação.
P. Quando devo usar cada tipo de ordenação?
R. O bubble sort é para ensinar, o insertion sort brilha em dados quase ordenados, o quicksort cobre a maior parte do uso geral (é o que o qsort() da biblioteca padrão usa), e o merge sort é ótimo para listas encadeadas e ordenação externa. O caminho usual de aprendizagem é bubble → insertion → quicksort.
P. O que é uma ordenação estável?
R. Uma ordenação estável preserva a ordem relativa de elementos que comparam iguais. Por exemplo, ao ordenar alunos por nota, alunos empatados mantêm a ordem original. Estáveis: bubble, insertion, merge. Instáveis: selection, quicksort, heap.
P. O que significa O(n log n)?
R. A complexidade de tempo descreve como o tempo de execução cresce conforme o tamanho da entrada n cresce. Com O(n²), dobrar n quadruplica o tempo; O(n log n) cresce muito mais devagar. O(n) é linear, O(n log n) é rápido na prática, e O(n²) ou pior normalmente só é aceitável para entradas pequenas.
Quiz Rápido
Teste seu entendimento desta aula.
Q1. Qual a complexidade no pior caso do bubble sort?
O(n)
O(n log n)
O(n²)
O bubble sort compara e troca elementos adjacentes repetidamente, resultando em O(n²) no pior caso.
Q2. Qual a complexidade no caso médio do quicksort?
O(n)
O(n log n)
O(n²)
O quicksort usa divisão e conquista em torno de um pivô, dando O(n log n) na média. No pior caso, pode degradar para O(n²).
Q3. O que é uma ordenação estável?
Uma ordenação que não quebra
Uma ordenação que preserva a ordem de elementos iguais
Uma ordenação que é sempre a mais rápida
Uma ordenação estável preserva a ordem relativa de elementos com chaves iguais. O merge sort é estável; o quicksort não.