Ordenação
Insertion sort: arrumando cartas na mão
Guarda, empurra, encaixa.
Na vida real
Jogando baralho, você pega uma carta nova (guarda), empurra pra direita as cartas maiores que ela e encaixa a nova no buraco que sobrou. As cartas da esquerda estão sempre arrumadas.
Código
for (i = 1; i < n; i++) { chave = v[i]; j = i - 1; while (j >= 0 && v[j] > chave) { v[j + 1] = v[j]; j--; } v[j + 1] = chave;}passo 1 de 26
Também dá pra usar as setas ← e → do teclado.
O que o computador está vendo
Vetor (gavetas)
5[0](já está no lugar certo)
1[1]
4[2]
2[3]
Tela
Mão de cartas: 5 1 4 2. A primeira carta sozinha já está "arrumada".
- comparando
- acabou de mudar
- já está no lugar certo
Peça por peça
| Peça | O que significa |
|---|---|
| i = 1 | Começa na segunda carta: a primeira sozinha já está arrumada. |
| chave | A carta que você pegou na mão. |
| while | Enquanto a carta da esquerda for maior, empurra. |
| j >= 0 | Pra não sair do vetor pela esquerda. |
| v[j + 1] = chave | Encaixa no buraco. |
Pra decorar: "guarda, empurra, encaixa". É o único dos três que começa em i = 1 e usa while.
Teste rápido: Qual ordenação usa while dentro do for?