Ordenação: bubble, selection e insertion sort passo a passo

Questões de algoritmos costumam dar um vetor desordenado e perguntar como ele fica após a segunda passada de um método, ou quantas trocas foram feitas. A única forma segura de acertar é simular à mão, com método. Este guia faz isso com os três ordenadores elementares sobre o mesmo vetor, e todos os estados e contagens foram obtidos executando o código em um teste.

Vetor de partida: 5, 2, 9, 1, 6 (cinco elementos, ordem crescente desejada).

Bubble sort (bolha)

A cada passada, compara pares vizinhos e troca os que estão fora de ordem. O maior elemento “flutua” até o final em cada passada.

Passada	Estado do vetor ao final
1	2, 5, 1, 6, 9
2	2, 1, 5, 6, 9
3	1, 2, 5, 6, 9
4	1, 2, 5, 6, 9 (nenhuma troca: pode parar)

Na primeira passada: compara 5 e 2 (troca), 5 e 9 (não), 9 e 1 (troca), 9 e 6 (troca). O 9 chegou ao fim. Total no teste: 10 comparações e 5 trocas. Esse número de trocas não é coincidência: cada troca de vizinhos elimina exatamente uma inversão (par fora de ordem), e o vetor tinha 5 inversões: (5,2), (5,1), (2,1), (9,1) e (9,6).

Com a otimização “parar quando uma passada não troca nada”, um vetor já ordenado exige apenas uma passada: no vetor 1, 2, 3, 4, 5 foram 4 comparações e nenhuma troca.

Selection sort (seleção)

A cada passo, procura o menor elemento do trecho ainda não ordenado e o troca com o primeiro desse trecho.

Passo	Menor achado	Estado ao final
1	1 (posição 3)	1, 2, 9, 5, 6
2	2 (já está no lugar)	1, 2, 9, 5, 6
3	5	1, 2, 5, 9, 6
4	6	1, 2, 5, 6, 9

Veja o passo 1: o 1 foi trocado com o 5 (que estava na posição 0), e por isso o 5 foi parar no meio do vetor. Isso mostra que o selection sort não é estável: elementos iguais podem inverter a ordem relativa. No teste, foram 10 comparações e 3 trocas. O número de comparações não depende do estado inicial: para n elementos, são sempre n(n-1)/2, que para n igual a 5 dá 10.

Insertion sort (inserção)

Mantém um trecho inicial ordenado e, a cada passo, pega o próximo elemento e o insere na posição correta dentro desse trecho, deslocando os maiores para a direita (como organizar cartas na mão).

Passo	Elemento inserido	Estado ao final
1	2	2, 5, 9, 1, 6
2	9	2, 5, 9, 1, 6
3	1	1, 2, 5, 9, 6
4	6	1, 2, 5, 6, 9

No teste: 7 comparações e 5 deslocamentos (o mesmo número de inversões, de novo). Se o vetor já está ordenado, cada elemento só é comparado uma vez com o anterior: 4 comparações e nenhum deslocamento em cinco elementos, o que faz do insertion sort o melhor dos três em listas quase ordenadas.

Casos extremos lado a lado

Resultados do teste nos vetores 1, 2, 3, 4, 5 (já ordenado) e 5, 4, 3, 2, 1 (inverso):

Método	Vetor ordenado	Vetor inverso
Bubble (com parada antecipada)	4 comparações, 0 trocas	10 comparações, 10 trocas
Selection	10 comparações, 0 trocas	10 comparações, 2 trocas
Insertion	4 comparações, 0 deslocamentos	10 comparações, 10 deslocamentos

Note que o selection faz poucas trocas mesmo no pior caso (no máximo uma por passo), o que importa quando trocar é caro. E no vetor inverso, bubble e insertion fazem uma troca por inversão: 10 inversões em 5 elementos.

Resumo de complexidade

Método	Melhor caso	Pior caso	Estável?
Bubble	O(n), com parada antecipada	O(n²)	sim
Selection	O(n²)	O(n²)	não
Insertion	O(n)	O(n²)	sim

Os três têm custo quadrático no pior caso, por isso servem para listas pequenas. Para listas grandes, usam-se métodos com custo em torno de O(n log n), como merge sort e quicksort (este com pior caso quadrático). A notação está explicada em busca sequencial e binária e Big O. “Estável” significa que elementos de chave igual mantêm sua ordem relativa original.

Como resolver na prova

Copie o vetor e numere as posições.
Execute exatamente o procedimento do método, uma passada de cada vez, reescrevendo o vetor.
Confira se o enunciado conta “passada” como varredura completa ou como cada comparação.
Se pedirem trocas, lembre da relação com inversões no bubble e no insertion.

Erros comuns

Misturar as regras: no bubble, só se comparam vizinhos; no selection, procura-se o menor do resto.
Esquecer que, ao final da passada k do bubble, os k maiores já estão no lugar.
Contar a “troca” do selection quando o menor já está na posição certa (não há troca nesse caso).
Dizer que todo ordenador quadrático é igualmente lento em todos os casos: o insertion é linear no melhor caso.
Esquecer que algumas bancas ordenam de forma decrescente.

Fontes e atualização

Não há norma oficial brasileira sobre algoritmos; o conteúdo segue a literatura clássica de estruturas de dados. Todos os estados e contagens vieram da execução dos algoritmos no vetor indicado. Variações de implementação (início da contagem, parada antecipada) mudam números: confira o enunciado e o edital.

Próximos passos

Compare com a busca em busca sequencial e binária.
Estude pilha, fila e lista com exemplos executados.
Veja como árvores guardam dados ordenados em árvore binária de busca e percursos.