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 {5,3}

{3,6}, {4,8}, {1,2} e {3,5}
EXEMPLO APLICADO
Exemplo para ordenar 6, 3, 4, 8, 1, 2, 5, 3

Etapa 3 Combinar
 Juntar as duas metades em um único conjunto já
classificado;

Por fim o algoritmo irá juntar os pares e ordenar através
da recursividade da etapa 2:

{3,6}, {4,8}, {1,2} e {3,5}

{3,4,6,8} e {1,2,3,5}
Observação: a etapa 3 esta contida na etapa 2
EXEMPLO APLICADO

Por fim o algoritmo é repetido algumas vezes até chegar na
ordenação correta:

Entrada: 6, 3, 4, 8, 1, 2, 5, 3

Processamento 1: {6,3}, {8,4}, {1,2} e {5,3}

Processamento 2: {6,3}, {8,4}, {1,2} e {5,3}

Processamento 3: {3,6}, {4,8}, {1,2} e {3,5}

Processamento 4: {3,4,6,8} , {1,2,3,5}

Processamento 5: {1, 2, 3, 3, 4, 5, 6, 8}

Saída: 1, 2, 3, 3, 4, 5, 6, 8
LIMITES DO MERGE SORT

Quando utiliza-se muitos dados, o merge sort não aconselhado devido aos
inúmeros cálculos realizados através da recursão pelo processador e
também aloca o dobro de memória por usar um array auxiliar.

Isto pode acarretar em mais tempo de execução onde outros métodos podem
ser mais eficientes.

Abaixo gráfico comparativo do tempo médio do algoritmo :
http://www.slideshare.net/OnOSJunior/anlise-emprica-de-algoritmos-deordenao
CONCLUSÃO


O objeto de estudo deste trabalho, algoritmo
Merge Sort ou mistura de dados, mostra-se um
algoritmo de ordenação um pouco complexo
devido a utilização de recursividade, embora
ainda este demonstre ser útil em diversos casos
onde é exigido uma ordenação.
Através deste trabalho, também pudemos
verificar que existem diversos algoritmos para
ordenação de dados, onde dentre eles o merge
sort que apresenta um nível de utilização médio
baixo.
REFERÊNCIAS

http://pt.wikipedia.org/wiki/Merge_sort#C.C3.B3digo_em_C.2B.2B

http://www.dct.ufms.br/~marco/aed22008/aula04_4.pdf

http://www.dca.fee.unicamp.br/~andreric/arquivos/Algoritmos_de_ordenacao.pdf

http://www.slideshare.net/OnOSJunior/anlise-emprica-de-algoritmos-de-ordenao

http://imasters.com.br/artigo/13015/desenvolvimento/principais-algoritmos-de-ordenacao-de-dados

http://www.lcad.icmc.usp.br/~nonato/ED/Ordenacao/node52.htm