Questão #11095712016

Algoritmos e Estrutura de Dados (TI)

O mergesort é um algoritmo de ordenação do tipo

dividir-para-conquistar. Sua ideia básica consiste

em dividir o problema em vários subproblemas, e

resolver esses subproblemas por meio da

recursividade e, em seguida,após todos os subproblemas

terem sido resolvidos,ocorre a conquista,

que é a união das resoluções dos subproblemas.O

algoritmo mergesort, apresentado em seguida, está

codificado em C/C++.Esse algoritmo ordena o vetor

1. voidmergesort(int a[], int p, int r) 2. { 3. inti,j,k,m; 4. if (r gt; p) 5. { 6. m = (r + p)/2; 7. … 8. … 9. for (i = m+1; igt; p; i--) b[i-1] = a[i-1]; 10. for (j = m; j lt; r; j++) b[r+m-j] = a[j+1]; 11. ... 12. ... 13. } 14. }

A 7.mergesort(a, p, m); 8.mergesort(a, m+1, r); … 11.for (k = p; k lt;= r; k++) 12. a[k] = (b[i]lt;b[j]) lt; b[i++] : b[j--]; B 7.mergesort(a, p, m+1); 8.sort(a, m+1, r); ... 11.for (k = m; k lt;= r; k--) 12. a[k] = (b[i]lt;b[j]) gt; b[i++] : b[j--]; C 7.mergesort(a, p, m); 8.mergesort(a, m+1, r); … 11.for (k = m; k lt;= m; k++) 12. a[m] = (b[m]lt;b[j]) gt; b[m++] : b[m--]; D 7.sort(a, p, m); 8.sort(a, m+1, r); ... 11.for (k = p; k lt;= r; k++) 12. a[k] = (b[i]lt;b[j]) gt; b[i++] : b[j--]; E 7.sort(a, p, m); 8.merge(a, m+1, r); ... 11.for(k = p; k lt;= r; k++) 12. a[k] = (b[i]lt;b[j]) gt; b[i++] : b[j--];

Algoritmos e Estrutura de Dados (TI)

Uma questão respondida. E as próximas?