Merge sort em três partes
objetivo Dividir em três partes em vez de duas, e contar toda chamada recursiva.
Em vez de dividir o vetor em duas metades, essa variação divide em três partes: n1 = n / 3, n2 = (n - n1) / 2, n3 = n - n1 - n2.
Ordena cada parte recursivamente e depois intercala a primeira com a segunda; esse resultado, intercala com a terceira. São duas chamadas de intercala por nível, não uma.
O desafio conta quantas vezes merge_sort3 é chamada no total — incluindo as chamadas com n < 2 (até as de tamanho 0). Uma variável global chamadas soma 1 a cada chamada, antes até de testar o caso base.
Onde todo mundo escorrega
- Contar depois do if (n < 2) perde as chamadas do caso base — o enunciado pede pra contar antes.
- Declarar os vetores com tamanho fixo 100 (não com n), senão a dica do enunciado some.
Desafio
Leia n e os n números. Implemente a função recursiva merge_sort3 que: se n < 2, não faz nada; senão divide em três partes (n1 = n / 3, n2 = (n - n1) / 2, n3 = n - n1 - n2), ordena cada uma recursivamente e intercala a parte 1 com a 2, e esse resultado com a 3. Conte quantas vezes merge_sort3 é chamada no total, incluindo as chamadas com n < 2.
Saída esperada: O vetor ordenado em uma linha e, na linha seguinte, "chamadas: X".
#include <stdio.h>
int chamadas = 0;
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; }
k = 0;
while (k < fim - ini) { v[ini + k] = aux[k]; k = k + 1; }
}
void merge_sort3(int v[], int ini, int n) {
// conte esta chamada ANTES do caso base
// caso base: n < 2
// divida em n1, n2 e n3, e chame merge_sort3 nas tres partes
// intercale a parte 1 com a 2, e esse resultado com a 3
}
int main() {
int v[100], n, i = 0;
scanf("%d", &n);
// leia os n numeros
merge_sort3(v, 0, n);
// imprima o vetor ordenado numa linha, e "chamadas: X" na linha seguinte
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.