Upload
duongnguyet
View
214
Download
0
Embed Size (px)
Citation preview
Grupo 4 apresenta:
ST364 Estruturas de Dados
Seminário
MERGESORTBlog - http://grupomergesort.blogspot.com
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Apresentação do Grupo
• André Pereira Giacon
• Dandara Contieri Folis
• Diego Narciso Hernandes
• Fernanda Cristina Spadotim
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Objetivo do Seminário
• Apresentar o conceito da ordenação MergeSort,demonstrar a sua performance em comparação comoutras ordenações e algumas aplicações.
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Estrutura da Apresentação
• Introdução
• Paradigma: Dividir para Conquistar
• Funcionamento
• Complexidade e Comparações
• Vantagens e Desvantagens
• Outras informações
• Conclusão
• Espaço para Tirar Dúvidas
• Finalização
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Um algoritmo que ordena um conjunto, geralmente representada num vetor, é chamado de algoritmo de ordenação
• Ordenar uma sequência: possibilidade se acessar seus dados de modo mais eficiente
Ordenação
Introdução
Fonte:Clip-Art
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Método inventado em 1945 por John Von Neumann
• Classificado como ordenação por partição
• Utiliza o Paradigma Dividir para Conquistar
O MergeSort
Introdução
Fonte:http://www.enseignement.pol
ytechnique.fr/informatique/images/V
on_Neumann_5.jpeg
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Não é in-place
• MergeSort possui ordenação estável
• Implementação Recursiva ou Interativa
Algumas Características
MergeSort
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Primeira vez usada por Anatolii Karatsuba em 1960
• Divisão do problema maior em problemas pequenos
• Abordagem:
– Divisão
– Conquista
– Combinação
Definição
Dividir Para Conquistar
http://www.viagemdeferias.com/joao
pessoa/fotos/mapa-do-brasil.gif
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Dividir: divide uma seqüência ao meio criando duas subsequências
• Conquistar: divide cada uma das duas subsequências recursivamente até que tenham tamanho um ou dois
• Combinar: funde as duas subsequências de volta em uma sequência ordenada
Aplicado ao MergeSort
Dividir Para Conquistar
MergeSort - Grupo 4 ST 364 – Estruturas de dados
1. Calcule o tamanho do vetor
2. Caso o tamanho do vetor > 2 elementos
I. Divida o vetor no meio
II. Ordene a primeira parte recursivamente
III. Ordene a segunda parte recursivamente
IV. Intercale as duas metades
3. Senão, caso tamanho = 2
I. Ordene o vetor comparando as posições
4. Devolva o vetor ordenado
Algoritmo
Dinâmica para o MergeSort
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Pseudocódigo – Parte 1
Funcionamento do MergeSort
MergeSort( n, X )
n = número de elementos
X = vetor para ordenação
T = variável auxiliar
Se n = 2
Se X[0] > X[1]
T X[0]
X[0] X[1]
X[1] T
Então
Então
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Pseudocódigo – Parte 2
Funcionamento do MergeSort
Senão Se n > 2
m [n/2]
Para i 0 Até m-1
Faça A[i] X[i]
Para i m até n-1
Faça B[i-m] X[i]
MergeSort( m, A )
MergeSort( n-m, B )
i 0
j 0
Para k 0 até n-1
Se A[i] ≤ B[j]
X[k] A[i]
i i + 1
X[k] B[j]
j j + 1
Então
Faça
Então
Senão
A = vetor auxiliar
B = vetor auxiliar
m = auxilia divisão do vetor
i,j = auxilia intercalação e
divisão
k = auxilia intercalação
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Complexidade:
• Teste comparativo
Características
Complexidade
Melhor caso O(n log2 n)
Médio caso O(n log2 n)
Pior caso O(n log2 n)
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Computador com as seguintes configurações:
– Processador Pentium D 2.8 Ghz FSB 800 Mhz
– 1 GB de memória RAM DDR 533 Mhz
– Placa Mãe Asus P5ND2
– Sistema Operacional Microsoft Windows XP Service Pack 3.
• Linguagem:C++
• Software: Microsoft Visual Studio Express 2008.
• Métodos Testados:
– MergeSort
– QuickSort
– BubbleSort
Teste
Comparações
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Resultados do Teste – Caso Médio com 100 elementos
Comparações
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Comparações
Resultados do Teste – Caso Médio com 10.000 elementos
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Resultados do Teste – Caso Médio com 100.000 elementos
Comparações
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Resultados do Teste – Tempo
Comparações
0,00001
0,00010
0,00100
0,01000
0,10000
1,00000
10,00000
100,00000
1000,00000
100 1.000 10.000 100.000
BubbleSort QuickSort MergeSort
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Vantagens e Desvantagens
• Vantagens:
– Útil para ordenação externa
– Pior caso: O (n log2 n)
– Aplicações com restrição de tempo
– Fácil implementação
• Desvantagens:
– Utiliza memória auxiliar
– Alto consumo de memória
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Eficiente para ordenar listas ligadas
MergeSort com Listas Ligadas:
Outras Informações
1 5 4 3 2
Ponteiros
Recursão Complexidade
1 2 3 4 5
MergeSort - Grupo 4 ST 364 – Estruturas de dados
• Pode ser utilizado como principio para a Ordenação Externa
• Implementação com programação paralela
Vale a pena saber:
Outras Informações
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Conclusão
• Estabilidade
• Método dividir para conquistar
• Utiliza a mesma complexidade para o melhor, médio e pior caso
• Fácil Implementação
• Vale a pena usar, só é necessário analisar quando
MergeSort - Grupo 4 ST 364 – Estruturas de dados
Espaço para Tirar Dúvidas
Fonte: http://www.truthdig.com/images/eartothegrounduploads/questions_for_bush500.jpg