QUESTIONÁRIO 07 - ED II

Ordenação – Método Mergesort

1)                 Por que o método mergesort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

Resposta:

O método de ordenação Mergesort também é conhecido como “dividir para conquistar” e significa  ordenação por mistura (fusão).

2)      A ordenação pelo método mergesort é um dos mais simples. Qual a principal característica do método ou como ele funciona?

Resposta:

Sua idéia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

3)      Qual é a classificação do método mergesort? Qual o seu grau de complexidade?

Resposta:

Método recursivo e sua ordem de complexidade do algoritmo recursivo deste método é O(n log n) .

4)      Dê exemplo de aplicação do método mergesort, com as comparações, trocas e iterações.

Resposta:

5)      Demonstre o código-fonte do método mergesort e comente o mesmo.

Resposta:

// A função mergesort rearranja o vetor v[p..r-1]

// em ordem crescente.

void

mergesort (int p, int r, int v[])

{

   if (p < r-1) {

      int q = (p + r)/2;

      mergesort (p, q, v);

      mergesort (q, r, v);

      intercala (p, q, r, v);

   }

}