E11.1 Escreva uma versão do algoritmo de inserção que tenha o seguinte invariante: no início de cada iteração, o vetor v[j+1..n-1] é crescente.
E11.2 Discuta a seguinte implementação do algoritmo Mergesort.
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); // 3
}
}
E11.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] fique crescente. Use mrg para implementar o algoritmo Mergesort.
E11.4 O algoritmo de inserção é estável?
O algoritmo de inserção é estável
se trocarmos a comparação
v[i] > x
por
v[i] >= x
no código?
E11.5 O algoritmo Mergesort é estável?