- Implemente o algoritmo da Intercalação (merge)
- Resolva a questão 3 da
Prova Substitutiva da Segunda prova de 2012-1
- Escreva uma função que receba vetores disjuntos x[0..m-1] e y[0..n-1],
ambos em ordem crescente, e produza um vetor z[0..m+n-1] que contenha o
resultado da intercalação dos dois vetores dados. (É claro que z estará em
ordem crescente). Escreva duas versões da função: uma iterativa e uma
recursiva.
- Um algoritmo de intercalação é estável se não altera a posição relativa de
elementos iguais. A função intercala1 discutida acima é estável? E se a
comparação "v[i] <= v[j]" for trocada por "v[i] < v[j]"?
- Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
i = p; j = q; k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
if (v[i] > v[j]) w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
while (j < r) w[k++] = v[j++];
for (i = p; i < r; ++i) v[i] = w[i-p];
- Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
i = p; j = q; k = 0;
while (i < q && j < r) {
if (v[i] <= v[j]) w[k++] = v[i++];
else w[k++] = v[j++];
}
while (i < q) w[k++] = v[i++];
for (i = p; i < j; ++i) v[i] = w[i-p];
- Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
i = p; j = q;
for (k = 0; k < r-p; ++k) {
if (j >= r || (i < q && v[i] <= v[j]))
w[k] = v[i++];
else
w[k] = v[j++];
}
for (i = p; i < r; ++i) v[i] = w[i-p];
- Critique a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas):
i = p; j = q; k = 0;
while (k < r-p) {
while (i < q && v[i] <= v[j])
w[k++] = v[i++];
while (j < r && v[j] <= v[i])
w[k++] = v[j++];
}
for (i = p; i < r; ++i) v[i] = w[i-p];