merge

SEGURANÇA DA INFORMAÇÃO - ESTRUTURA DE DADOS C++

MERGE SORT
DANIEL C. MERODE
NAIROBI S. DE OLIVEIRA

OBJETIVOS DA APRESENTAÇÃO


Sobre o Merge Sort (ordenação por mistura)



Descrição do Algoritmo



Exemplo Aplicado



Limites do Merge Sort



Conclusão



Referências

SOBRE O MERGE SORT (ORDENAÇÃO POR MISTURA)


Este algoritmo foi criado por John Von Neumann Matemático Húngaro/Estadunidense - em 1945.



É um dos algoritmos de ordenação que utiliza o método dividir para conquistar como ideia principal, sendo este um algoritmo com uma base bem matemática.



O objetivo do algoritmo é criar uma sequência ordenada a partir de outras duas já ordenadas.



Para tal, divide-se a sequência original em pares de dados, e ordena-se. Depois, agrupa-se em sequências de quatro elementos, e assim por diante até a sequência original estar separada em apenas duas partes.

DESCRIÇÃO DO ALGORITMO


O método Dividir consiste em organizar o problema em vários sub problemas, dividindo os valores de um vetor em outros dois subvetores de tamanho [v/2] e [v/2].



Na etapa Conquistar os dois subvetores são ordenados através da recursividade utilizando o Merge Sort.



A última etapa Combinar ocorre a união dos valores resolvidos e ordenados anteriormente através do método Conquistar.

http://pt.wikipedia.org/wiki/Merge_sort#C.C3.B3digo_em_C.2B.2B

EXEMPLO APLICADO
Exemplo para ordenar 6, 3, 4, 8, 1, 2, 5, 3


Etapa 1 Dividir


Dividir os dados em subsequências pequenas;



O algoritmo irá dividir em pares ordenados os valores informados: 

6, 3, 4, 8, 1, 2, 5, 3



{6,3}, {8,4}, {1,2} e {5,3}

EXEMPLO APLICADO
Exemplo para ordenar 6, 3, 4, 8, 1, 2, 5, 3


Etapa 2 Conquistar
 Classificar as duas metades antes divididas e, recursivamente ir aplicando o Merge Sort;


O algoritmo irá ordenar através da recursividade os pares: 

{6,3}, {8,4}, {1,2} e