24
Grupo 4 apresenta: ST364 Estruturas de Dados Seminário MERGESORT Blog - http://grupomergesort.blogspot.com

Grupo 4 apresenta: Seminário MERGESORT - ft.unicamp.br · representada num vetor, é chamado de algoritmo de ordenação •Ordenar uma sequência: possibilidade se acessar seus

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

MergeSort - Grupo 4 ST 364 – Estruturas de dados

Finalizando

• Confira o resumo do MergeSort, tire dúvidas para o projeto e mais informações em nosso blog:

http://grupomergesort.blogspot.com

• Agradecemos a todos pelo apoio e participação.

• Obrigado !