Aula05_MergeSort

Prévia do material em texto

Classificação e Pesquisa
MergeSort 
Ordenação pela intercalação
1
Prof. Antonio Felicio Netto
antonio.felicio@aedu.com
Merge Sort
- O merge sort, ou ordenação por intercalação, é um
exemplo de algoritmo de ordenação do tipo dividir “para
conquistar”;
- Dividir a tarefa em pequenas subtarefas
- Conquistar que é resolver cada subtarefa aplicando o 
algoritmo recursivamente;
2
algoritmo recursivamente;
- Combinar as soluções das subtarefas construindo assim a 
solução do problema como um todo;
- Tipicamente, algoritmos do tipo “Dividir para Conquistar” 
são recursivos;
Merge Sort
- Vantagem
Algoritmo de ordenação de simples implementação e fácil 
entendimento utilizando chamadas recursivas.
- Desvantagem
Alto consumo de memória, devido a série de chamadas 
3
Alto consumo de memória, devido a série de chamadas 
recursivas.
Merge Sort - conceito
- Considere um array A[1..n]. 
- O algoritmo consiste das seguintes fases
Dividir A em 2 sub-coleções de tamanho ≈ n/2
Conquistar: ordenar cada sub-coleção chamando 
MergeSort recursivamente
Combinar as sub-coleções ordenadas formando uma 
4
Combinar as sub-coleções ordenadas formando uma 
única coleção ordenada
- Se uma sub-coleção tem apenas um elemento, ela já está 
ordenada e configura o caso base do algoritmo
Merge Sort – Exemplo 01
7 5 2 4 1 6 3 0
7 5 2 4 1 6 3 0
entrada
0 1 2 3 4 5 6 7
2 4 5 7 0 1 3 6
saída
5
7 5 2 4 1 6 3 0
2 47 5 1 6 3 0
27 45 31 06
Dividir
2 4 5 7 0 1 3 6
2 45 7 1 6 0 3
27 45 31 06
Combinar
Merge Sort - Algoritmo
A rotina MergeSort abaixo ordena as posições i, i+1, … 
i+n–1 do array A[]
procecimento MergeSort (A [ ], i, n) 
inicio
se n > 1 então
inicio
6
m = n div 2
MergeSort (A, i, m)
MergeSort (A, i + m, n)
Merge (A, i, i + m, n)
fim
fim
Merge Sort - Algoritmo
procecimento Merge (A [ ], inicio, meio, final) 
variaveis
i, j, k, vetTemp[ ]: inteiro 
Inicio
i = inicio; j = meio; k = 0;
enquanto ((i <= meio) e (j <= final)) faça
inicio
se (A[i] < A[j]) então
inicio
enquanto (i <= meio) faça
inicio 
vetTemp [k] = A[i]; 
k = k + 1; i = i + 1; 
fim 
enquanto (j <= r) faça
inicio 
vetTemp[k] = A[j]; 
k = k + 1; j = j + 1; 
7
inicio
vetTemp [k] = A[i]; i = i + 1; 
fim
senao
inicio
vetTemp[k] = A[j]; j = j + 1; 
fim 
k = k + 1; 
fim 
k = k + 1; j = j + 1; 
fim 
para k := inicio até final faça
inicio
A[k] := vetTemp[k];
fim
fim 
Merge Sort - Considerações
- Complexidade de tempo: Θ(n log2 n)
- Complexidade de espaço: Θ(n)
- É possível implementar o merge sort utilizando somente 
um vetor auxiliar ao longo de toda a execução, tornando 
assim a complexidade de espaço adicional igual a 
8
assim a complexidade de espaço adicional igual a 
Θ(n log n). 
- É possível também implementar o algoritmo com espaço 
adicional Θ(n)
Merge Sort – Exemplo 2
- Dado um arranjo com n números naturais, ordenar estes 
números em ordem crescente.
9
Entrada: 95 48 70 86 21 37
Saída: 21 37 48 70 86 95
Merge Sort – Exemplo 2
Buscando dividir o problema – It 1
Entrada: 95 48 70 86 21 37
Parte 1 Parte 2
10
Merge Sort – Exemplo 2
Buscando dividir o problema – It 2
Entrada: 95 48 70 86 21 37
Parte 1 P2 Parte 2
11
Merge Sort – Exemplo 2
Realizando a ordenação - conquista
Entrada: 48 95 70 86 21 37
Conq P2 Parte 2
12
Merge Sort – Exemplo 2
Realizando intercalação (merge)
Entrada: 48 70 95 86 21 37
Intercalação Parte 2
13
Merge Sort – Exemplo 2
Buscando dividir o problema – It 2
Entrada: 48 70 95 86 21 37
Intercalação Parte 1 P2
14
Merge Sort – Exemplo 2
Realizando a ordenação - conquista
Entrada: 48 70 95 21 86 37
Intercalação Conq P2
15
Merge Sort – Exemplo 2
Realizando a intercalação
Entrada: 48 70 95 21 37 86
Intercalação Intercalação
16
Merge Sort – Exemplo 2
Realizando a intercalação
Saída: 21 37 48 70 86 95
Intercalação
17
Merge Sort – Exemplo 3 Vetor com 16 posições
6 2 8 5 10 9 12 1 15 7 3 13 4 11 16 14
2 6 8 5 10 9 12 1 15 7 3 13 4 11 16 14
2 6 5 8 10 9 12 1 15 7 3 13 4 11 16 14
2 5 6 8 10 9 12 1 15 7 3 13 4 11 16 14
2 5 6 8 9 10 12 1 15 7 3 13 4 11 16 14
2 5 6 8 9 10 1 12 15 7 3 13 4 11 16 14
2 5 6 8 1 9 10 12 15 7 3 13 4 11 16 14
1 2 5 6 8 9 10 12 15 7 3 13 4 11 16 14
18
1 2 5 6 8 9 10 12 15 7 3 13 4 11 16 14
1 2 5 6 8 9 10 12 7 15 3 13 4 11 16 14
1 2 5 6 8 9 10 12 7 15 3 13 4 11 16 14
1 2 5 6 8 9 10 12 3 7 13 15 4 11 16 14
1 2 5 6 8 9 10 12 3 7 13 15 4 11 16 14
1 2 5 6 8 9 10 12 3 7 13 15 4 11 14 16
1 2 5 6 8 9 10 12 3 7 13 15 4 11 14 16
1 2 5 6 8 9 10 12 3 4 7 11 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
• Dividir 
–Divide o array em duas partes.
Merge Sort – Exemplo 4
A L G O R I T H M S
divideA L G O R I T H M S
•Mergesort (divisão e conquista)
–Divide o array em duas partes.
–Realiza a ordenação.
Merge Sort – Exemplo 4
sort
A L G O R I T H M S
divideA L G O R I T H M S
A G L O R H I M S T
Merge Sort – Exemplo 4
merge
sort
A L G O R I T H M S
divideA L G O R I T H M S
A G L O R H I M S T
A G H I L M O R S T
•Intercala.
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H I
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H I L
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H I L M
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H I L M O
Merge Sort – Exemplo 4
auxiliary array
smallest smallest
A G L O R H I M S T
A G H I L M O R
first half
Merge Sort – Exemplo 4
auxiliary array
first half
exhausted smallest
A G L O R H I M S T
A G H I L M O R S
first half
Merge Sort – Exemplo 4
auxiliary array
first half
exhausted smallest
A G L O R H I M S T
A G H I L M O R S T
Exercício – Deve ser enviado até o dia 11/09/2011 as 23:59
Elabore um algoritmo que:
1 – Dado um vetor de 10 posições de nome vet que deve ser 
preenchido pelo usuário (através do comando leia), realize a 
ordenação de vet utilizando o método Merge Sort;
32
Exercício – Será trabalhado em laboratório no dia 12/09
Elabore um programa que:
1 - Realize a o preenchimento de um vetor de nome “vet” de 70 
posições com números randômicos inteiros distintos de 1 até 
5000. 
2 – Realize a ordenação utilizando o Método Merge Sort;
33
2 – Realize a ordenação utilizando o Método Merge Sort;
ATPS para o dia 19/09/2011 em sala
- Entregar versão impressa;
- Equipe de até 4 alunos;
- Faremos o sorteio das equipes que farão a apresentação das 
fases;
- Entregar Etapa Nº 1, passo 2, 3, e 4 (exceto algoritmo busca 
linear com sentinela):
Troca do passo 1: implementar a classe de geração de 
números randômicos em JAVA, inteiros.
34
números randômicos em JAVA, inteiros.
A classe deve possui um método de nome generatearray, que 
possui o seguinte corolário:
public int [] generatearray (int size,int low, int high, boolean unique)
Onde:
size: tamanho do vetor que deve ser gerado;
low: menor número contemplado no vetor;
high: maior número contemplado no vetor;
unique: se o vetorpode ter número repetidos (true sim, false não)