sábado, 22 de outubro de 2011

QUESTIONÁRIO 07 - 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 mergesort ou ordenação por mistura (fusão), é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

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: Complexidade de tempo. É (n log2 n). É possível implementar o mergesort utilizando somente um vetor auxiliar ao longo de toda a execução.

      3) Qual é a classificação do método mergesort? Qual o seu grau de complexidade?
      Resposta: O   Mergesort é classificado como ordenação por partição, que parte do princípio de "dividir para conquistar". Este princípio é uma técnica que foi utilizada pela primeira vez por Anatolii Karatsuba em 1960 e consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente. 
      Esta técnica realiza-se em três fases:
      Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva. 
      Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
     Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn). Os dois representantes mais ilustres desta classe são o quicksort e o mergesort.
     
      4) Dê exemplo de aplicação do método mergesort, com as comparações, trocas e iterações.
     

      5) Demonstre o código-fonte do método mergesort e comente o mesmo.
                              
Clique na figura para visualizar

Nenhum comentário:

Postar um comentário