Dados dois vetores ordenados de valores int
(de tamanho
) e
(de tamanho m), escrever um programa que determina e mostra o vetor ordenado C que contém todos os elementos de AeB. Considerar que
.
Passo 1
O enunciado pede para juntar dois vetores ordenados de inteiros,
de tamanho
e
de tamanho
, num único vetor ordenado
. O conteúdo aqui é o algoritmo de mesclagem (merge) de listas ordenadas e vamos precisar usar dois ponteiros (índices) para percorrer
e
simultaneamente.
Passo 2
Vamos inicializar três índices:
para percorrer
,
para percorrer
, e
para preencher
. Também criamos
com tamanho
.
Enquanto e
, comparamos
e
. Se
, atribuímos
e incrementamos
e
. Caso contrário, atribuímos
e incrementamos
e
.
Quando sair desse laço, um dos vetores já foi totalmente copiado. Então copiamos o que sobrou do outro vetor em . Ou seja, enquanto
, fazemos
, incrementando
e
; e enquanto
, fazemos
, incrementando
e
.
Enquanto
Quando sair desse laço, um dos vetores já foi totalmente copiado. Então copiamos o que sobrou do outro vetor em
Passo 3
Ao final,
estará totalmente preenchido e ordenado. Basta imprimir ou retornar o vetor
.
Resposta
Segue o pseudocódigo do programa de mesclagem:
// Entrada: A[1..n] e B[1..m], ambos ordenados, com n>m
i ← 1; j ← 1; k ← 1
alocar C[1..n+m]
// Mescla enquanto houver elementos em A e B
enquanto i ≤ n e j ≤ m faça
se A[i] ≤ B[j] então
C[k] ← A[i]
i ← i + 1
senão
C[k] ← B[j]
j ← j + 1
fim se
k ← k + 1
fim enquanto
// Copia o restante de A, se existir
enquanto i ≤ n faça
C[k] ← A[i]
i ← i + 1
k ← k + 1
fim enquanto
// Copia o restante de B, se existir
enquanto j ≤ m faça
C[k] ← B[j]
j ← j + 1
k ← k + 1
fim enquanto
// Saída: vetor C[1..n+m] ordenado