Ordenação: bubble, selection e insertion
Colocando um array em ordem
- Ordenação reorganiza uma matriz para que os itens fiquem do menor para o maior.
- Ordenamos no local: movemos itens dentro da mesma matriz, sem valor de retorno.
- Três métodos clássicos fazem isso: ordenação bolha, inserção e seleção.
Trocando dois elementos
- Toda ordenação precisa trocar dois itens. Salve um em temporário, depois sobrescreva.
int t = a[i]; a[i] = a[j]; a[j] = t;troca as posiçõesiej.- Esquecer o temporário perde um dos valores — sempre mantenha-o.
Bubble sort
- Passe pela matriz e compare cada par de vizinhos:
a[j]ea[j + 1]. - Se estiverem na ordem errada, troque-os. O maior valor "borbulha" para o final.
- Repita as passagens até que toda a matriz esteja em ordem.
Insertion sort
- Trate a parte esquerda da matriz como já ordenada, e cresça-a um item de cada vez.
- Pegue o próximo item como chave, desloque os itens maiores ordenados para a direita, depois insira a chave no espaço.
- É assim que muitas pessoas ordenam cartas na mão.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Erros comuns
- Bolha, seleção e inserção são todas O(n²).
- Rastreie um array pequeno à mão para verificar sua ordenação.
Agora você tenta
- Ordene ascendente (menores primeiro), no local, sem valor de retorno.
- O verificador testa várias matrizes, incluindo negativas e uma já ordenada.
- Não escreva um
main— o verificador fornece um.
Assista uma ordenação rodar
Bubble / selection / insertion todos comparam e trocam para ordenar.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete void swap(int a[], int i, int j) para trocar os itens nos índices i e j, in-place (sem retorno). Não escreva um main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete void bubble_sort(int a[], int n) para ordenar o array em ordem crescente, in-place, usando bubble sort. Não escreva um main.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Complete void insertion_sort(int a[], int n) para ordenar o array em ordem crescente, in-place, usando insertion sort (pegue cada item como chave e desloque itens maiores para a direita). Não escreva um main.
Clique em Executar para ver a saída aqui.