Insertion sort
objetivo Pegar um elemento e encaixar no lugar certo, como quem arruma carta na mão.
Considere que a primeira posição já está ordenada. Pegue o próximo elemento e guarde numa variável chamada chave.
Volte comparando com os de trás. Enquanto o de trás for maior que a chave, ele anda uma casa pra direita, abrindo espaço.
Quando achar alguém menor ou igual, ou chegar no começo do , a chave entra no buraco que sobrou, na posição j + 1.
exemplo.cclique numa linha pra entender ela
Onde todo mundo escorrega
- Escrever v[j] = chave no fim, sem o mais um, apaga o elemento errado.
- Inverter a ordem das condições do while pode ler memória fora do vetor.
Desafio
Escreva insertion_sort, que coloca o vetor em ordem crescente usando o método da inserção. Sem usar a função trocar.
void insertion_sort(int v[], int n)o que a função tem que devolver
| chamada | saída esperada |
|---|---|
| v = {5, 2, 4, 6, 1}imprimirVetor(v, 5) | 1 2 4 5 6 |
| v = {3, 1, 2}imprimirVetor(v, 3) | 1 2 3 |
| v = {2, 1}imprimirVetor(v, 2) | 1 2 |
a sua função
linha 1
void insertion_sort(int v[], int n) {
// chave, deslocamento e encaixe
}Ctrl+Enter (Cmd+Enter no Mac) roda. Esc sai do editor.
aperte Rodar pra ver a saída aqui
Dicas
Tenta sozinho primeiro. Travou de verdade, abre a primeira.