Merge sort com rastro
objetivo Imprimir o vetor a cada intercalação, pra ver a recursão virar código.
O merge sort já apareceu na aula visual: divide o vetor no meio, ordena cada metade recursivamente e junta as duas com uma função de intercalar. Aqui o desafio é outro: fazer o código mostrar o que está fazendo.
Use meio = (fim - ini) / 2: a primeira metade fica com meio elementos, a segunda com o resto. O caso base é um trecho com 0 ou 1 elemento (fim - ini <= 1), que já está ordenado.
Assim que a função intercala termina de juntar um trecho, ela imprime merge: seguido dos elementos recém-ordenados. No fim do programa, depois do merge_sort completo, imprime final: com o todo.
As linhas merge: saem na ordem da árvore de chamadas: de baixo pra cima, da esquerda pra direita. Vale desenhar essa árvore no papel antes de programar.
Onde todo mundo escorrega
- intercala só funciona se as duas metades já estiverem ordenadas: merge_sort tem que chamar nas duas metades ANTES de chamar intercala.
- Contar o tamanho do trecho com fim - ini (não com fim - ini + 1): fim é o índice depois do último elemento, não entra no trecho.
Desafio
Implemente o merge_sort recursivo (ordem crescente) usando a intercala com rastro. Logo depois de cada intercalação, ela já imprime "merge: ...". No final do programa, depois do merge_sort completo, imprima "final: ..." com o vetor todo. Leia n e depois os n números.
Saída esperada: Uma linha "merge: ..." por intercalação, na ordem da recursão, e por fim "final: ..." com o vetor ordenado.
#include <stdio.h>
void intercala(int v[], int ini, int meio, int fim) {
int aux[100], i = ini, j = meio, k = 0;
while (i < meio && j < fim) {
if (v[i] <= v[j]) { aux[k] = v[i]; i = i + 1; }
else { aux[k] = v[j]; j = j + 1; }
k = k + 1;
}
while (i < meio) { aux[k] = v[i]; i = i + 1; k = k + 1; }
while (j < fim) { aux[k] = v[j]; j = j + 1; k = k + 1; }
printf("merge:");
k = 0;
while (k < fim - ini) {
v[ini + k] = aux[k];
printf(" %d", aux[k]);
k = k + 1;
}
printf("\n");
}
// trecho de ini ate fim - 1 (fim nao entra)
void merge_sort(int v[], int ini, int fim) {
// caso base: 0 ou 1 elemento
// divide no meio e chama merge_sort nas duas metades
// junta as duas metades com intercala
}
int main() {
int v[100], n, i = 0;
scanf("%d", &n);
// leia os n numeros
merge_sort(v, 0, n);
printf("final:");
// imprima o vetor todo, com espaco antes de cada numero
printf("\n");
return 0;
}Ctrl+Enter (Cmd+Enter no Mac) roda. Esc sai do editor.
O que o seu scanf vai ler quando você apertar Rodar.
Dicas
Tenta sozinho primeiro. Travou de verdade, abre a primeira.