E13.1 Considere a seguinte variante do Mergesort. (Suponha que intercala funciona como nas notas de aula: recebe vetores crescentes v[p..q-1] e v[q..r-1] e rearranja v[p..r-1] em ordem crescente.) Ela está correta? Quanto tempo consome?
void mergesort5 (int p, int r, int v[]) {
if (p < r-1) {
int q = r - 1;
mergesort5 (p, q, v);
intercala (p, q, r, v);
}
}
E13.2 Discuta a seguinte implementação do Mergesort, que promete colocar v[p..r-1] em ordem crescente. (Suponha que intercala funciona como nas notas de aula: recebe vetores crescentes v[p..q-1] e v[q..r-1] e rearranja v[p..r-1] em ordem crescente.)
void mergesort2 (int p, int r, int v[]) {
if (p < r) {
int q = (p + r) / 2; // 1
mergesort2 (p, q, v); // 2
mergesort2 (q, r, v); // 3
intercala (p, q, r, v); // 4
}
}
E13.3 Suponha que sua biblioteca tem uma função mrg (p, q, r, v) que funciona assim: recebe um vetor v tal que v[p..q-1] e v[q..r] são crescentes e rearranja o vetor de modo que v[p..r] (note os índices!) fique crescente. Use mrg para implementar o algoritmo Mergesort.
E13.4 Submeta o vetor 99 55 33 77 indexado por 1..4 à função quicksort vista em aula. Mostre a sequência de invocações da função, com a devida indentação.
E13.5
A seguinte implementação do Quicksort está correta?
Essa implementação partiu da implementação básica tradicional
e fez as seguintes alterações:
eliminou a segunda invocação da função quicksort
e trocou o if
por um while
.
Se a implementação estiver correta,
mostre que ela faz exatamente a mesma coisa
que a versão recursiva básica;
se estiver errada, mostre um contra-exemplo.
// Rearranja v[p..r] em ordem crescente.
void quicksrt (int v[], int p, int r) {
while (p < r) {
int j = separa (v, p, r);
quicksrt (v, p, j-1);
p = j + 1;
}
}
E13.6 Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j] ≤ 0 e v[j+1..r] > 0 para algum j em p-1..r (é claro que a função deve devolver j). Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Faz sentido exigir que v[j] seja 0?