- Faça um programa que receba dois vetores com N números, no qual cada vetor tem seus valores em ordem crescente (não precisa validar) e depois gere um terceiro vetor ordenado com os números dos dois vetores. Exemplo: vet1
e vet2
resultaria em
.
Passo 1
O enunciado pede um programa que receba dois vetores de tamanho
, ambos já ordenados em ordem crescente, e gere um terceiro vetor de tamanho
contendo todos os elementos dos dois vetores também em ordem crescente. O conteúdo é o algoritmo de “merge” de duas sequências ordenadas, que usa dois ponteiros para percorrer simultaneamente os dois vetores e construir o vetor resultante.
Passo 2
Inicializamos três índices:
para percorrer o primeiro vetor,
para o segundo, e
para o vetor resultado. Comparamos repetidamente o elemento atual de cada vetor e colocamos o menor em
, incrementando o respectivo ponteiro e também
.
Passo 3
Quando um dos vetores chega ao fim (isto é,
ou
), não há mais comparações a fazer. Nesse ponto copiamos todos os elementos restantes do outro vetor diretamente para
.
Passo 4
Ao final teremos
e
completamente preenchido em ordem crescente. Basta então imprimir ou retornar esse vetor.
Resposta
#include <stdio.h>
#include <stdlib.h>
int main() {
int N;
scanf("%d", &N);
int *vet\(1\) = malloc(N * sizeof(int));
int *vet\(2\) = malloc(N * sizeof(int));
int *vet\(3\) = malloc(\(2\) * N * sizeof(int));
// Leitura dos dois vetores, cada um já ordenado
for(int i \(=0\); i < N; i\(++\)) {
scanf("%d", &vet\(1\)[i]);
}
for(int i \(=0\); i < N; i\(++\)) {
scanf("%d", &vet\(2\)[i]);
}
// Merge dos dois vetores
int i \(=0\), j \(=0\), k \(=0\);
while(i < N && j < N) {
if(vet\(1\)[i] \(<=\) vet\(2\)[j]) {
vet\(3\)[k\(++\)] \(=\) vet\(1\)[i\(++\)];
} else {
vet\(3\)[k\(++\)] \(=\) vet\(2\)[j\(++\)];
}
}
// Copia o que restou em vet\(1\)
while(i < N) {
vet\(3\)[k\(++\)] \(=\) vet\(1\)[i\(++\)];
}
// Copia o que restou em vet\(2\)
while(j < N) {
vet\(3\)[k\(++\)] \(=\) vet\(2\)[j\(++\)];
}
// Impressão do vetor resultante
for(int idx \(=0\); idx < \(2\)*N; idx\(++\)) {
printf("%d ", vet\(3\)[idx]);
}
printf("\n");
free(vet\(1\));
free(vet\(2\));
free(vet\(3\));
return \(0\);
}