3-Ordenação-MergeSort1

Prévia do material em texto

Algoritmo MergeSort
Estrutura de Dados II
Prof Jairo Francisco de Souza
Intercalação
 Generalidades
  Intercalação é o processo através do qual diversos arquivos 
seqüenciais classifcados por um mesmo critério são 
mesclados gerando um único arquivo seqüencial                 
 Algoritmo Básico
 De cada um dos arquivos a intercalar basta ter em memória   
um  registro.  Considera-se cada arquivo como uma pilha, e o 
registro em memória seu topo
 Em cada iteração do algoritmo e leitura dos registros, o topo 
da pilha com menor  chave  é  gravado, e substituído pelo seu 
sucessor. Pilhas vazias têm topo igual a high value
 O algoritmo termina quando todos os topos da pilha tiverem 
high value
Intercalação
 Outra forma de intercalação é mesclar dois 
vetores (ordenados previamente)
 O resultado é um vetor ordenado, com os 
elementos dos vetores usados na mesclagem
11 33 55 55 77 99 99
Vetor 1
22 44 77 88
Vetor 2
11 22 33 44 55 55 77 77 88 99 99
Vetor_Resultado
Intercalação
 Inicialmente, para que aconteça a intercalação (ou merge), 
os elementos dos dois vetores devem ser copiados para 
apenas um vetor 
 Para execução do algoritmo de intercalação, o índice de 
início do segundo vetor e o tamanho do novo vetor devem 
ser encontrados
11 33 55 55 77 99 99 22 44 77 88
11 33 55 55 77 99 99
Vetor 1
22 44 77 88
Vetor 2
11 22 33 44 55 55 77 77 88 99 99
União dos Vetores
Inicio_Vet_2
Inicio Fim
Intercalação
Intercalação
 A intercalação deve ser usada também quando há 
necessidade de unir dados de dois arquivos de dados
 Desta maneira, os dados poderiam ser acessados por meio 
de suas estruturas
 Através de comandos de manipulação de arquivos, os dados 
entre os arquivos poderiam ser intercalados, gerando um 
novo arquivo de dados
 Neste caso, o desenvolvedor deve se preocupar 
principalmente com a coincidência de chaves primárias, e 
realizar o tratamento das transações problemáticas
Algoritmo de Intercalação
intercala (inteiro inicio_vet, inteiro inicio_vet_2, inteiro fim_vet, inteiro vetor[]) 
{
 inteiro indice_inicio, indice_inicio_vet_2, indice_aux;
 inteiro *vetor_aux;
 vetor_aux = (inteiro *) aloca_memoria (fim_vet * sizeof (inteiro));
 indice_inicio = inicio_vet;
 indice_inicio_vet_2 = inicio_vet_2;
 indice_aux = 0;
 Enquanto (indice_inicio < inicio_vet_2 e indice_inicio_vet_2 < fim_vet) 
 {
 Se (vetor[indice_inicio] <= vetor[indice_inicio_vet_2]) 
 { 
 vetor_aux [indice_aux] = vetor[indice_inicio];
 indice_aux = indice_aux + 1;
 indice_inicio = indice_inicio + 1;
 } senão { 
 vetor_aux [indice_aux] = vetor[indice_inicio_vet_2];
 indice_aux = indice_aux + 1;
 indice_inicio_vet_2 = indice_inicio_vet_2 + 1;
 }
 }
 
 Enquanto (indice_inicio < inicio_vet_2) {
 vetor_aux [indice_aux] = vetor[indice_inicio];
 indice_aux = indice_aux + 1;
 indice_inicio = indice_inicio + 1;
 }
 
 Enquanto (indice_inicio_vet_2 < fim_vet) {
 vetor_aux [indice_aux] = vetor[indice_inicio_vet_2];
 indice_aux = indice_aux + 1;
 indice_inicio_vet_2 = indice_inicio_vet_2 + 1;
 }
 
 Para (indice_inicio = inicio_vet; indice_inicio < fim_vet; indice_inicio++) {
 vetor[indice_inicio] = vetor_aux [indice_inicio - inicio_vet];
 }
 
 liberar_memoria (vetor_aux);
}
Intercalação usada para ordenação
 Algoritmo MergeSort utiliza a idéia de intercalação para 
ordenar registros.
 Algoritmo criado por von Neumann
 Complexidade O(NlogN) no caso médio e pior
 No pior caso é mais rápido do que o QuickSort
 Exemplo: Ordenar 10000 chaves:
 Algoritmos de O(N2): 100.000.000 comparações
 MergeSort: 40.000 comparações
MergeSort
A idéia central é unir dois arrays que já 
estejam ordenados. Ou seja, unir dois 
arrays A e B já ordenados e criar um terceiro 
array C que contenha os elementos de A e 
B já ordenados na ordem correta.
O foco inicial é no processo de junção dos 
arrays e posteriormente vamos trabalhar o 
processo de ordenação
Cenário
Considere que temos dois arrays já 
ordenados A e B que não precisam ser do 
mesmo tamanho onde A possui 4 elementos 
e B possui 6 elementos. Eles serão unidos 
para a criação de um array C com 10 
elementos ao final do processo de união
Cenário
23 47 81 95
7 14 39 55 62 74
7 14 23 39 47 55 62 74 81 95
23 < 7 ? 23 < 14 ? 47 < 39 ? 81 < 55 ? 81 < 62 ?
81 < 74 ?
Não há 
elementos 
em B
23 < 39 ? 47 < 55 ?
A
B
C
Ordenação
A idéia do método MergeSort é dividir um 
array ao meio, ordenar cada metade e 
depois unir estas duas metades novamente 
formando o array original, porém ordenado.
Como seria feita essa divisão e ordenação 
para que as metades possam ser unidas?
RECURSIVIDADE!
Ordenação
O algoritmo MergeSort
 O algoritmo divide a sequência original em pares de 
dados, classifcando e intercalando os elementos das 
partições
 Três passos são fundamentais para a execução do 
mergesort:
 Dividir: Dividir os dados em subsequências pequenas; 
 Conquistar: Classifcar as duas metades recursivamente 
aplicando o mergesort; 
 Combinar: Juntar as duas metades em um único conjunto já 
classifcado
O algoritmo MergeSort
 Dividir para conquistar
 O algoritmo é executado de forma recursiva
 Primeiro ordenar a primeira metade, em seguida a 
segunda metade
mergesort(inteiro *vetor,inteiro inicio,inteiro fim)
{
 inteiro meio;
 Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
}
O algoritmo MergeSort
 Considere o vetor abaixo:
26 69 25 53 59 27 41 0 33 16 35 43
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
26 69 25 53 59 27
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
26 69 25 53 59 27
26 69 25
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25
26 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25
26 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
26 69 25
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
26 69 25
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25
26 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25
26 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor,inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25 26
69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
53 59 27
25 26 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 6925 26 69 27
53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69 27
53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69
53 59 27
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69
53 59 27
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69 27
53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69 27 53
59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69 27 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 69 27 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25
26 69 27 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25
26 69 27 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26
69 27 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 27
69 53 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 27 53
69 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 27 53
69 59
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 27 53 59
69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
41 0 33 16 35 43
25 26 27 53 59 69
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 41 0 33 16 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
41 0 33
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
33
41 0
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
33
41 0
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
33
41 0
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
0 41 33
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
0 41 33
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
0
41 33
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
0 33
41
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 16 35 43
0 33 41
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 43
16 35
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 43
16 35
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 43
16 35
...
Se (inicio < fim) {
meio = (inicio + fim)/ 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 43
16
35
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41
16 35
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
43
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41
16 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 16
35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 16 35
43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69
0 33 41 16 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0
33 41 16 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0 16
33 41 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0 16 33
41 35 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0 16 33 35
41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0 16 33 35 41
43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
25 26 27 53 59 69 0 16 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0
25 26 27 53 59 69 16 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16
25 26 27 53 59 69 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25
26 27 53 59 69 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26
27 53 59 69 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27
53 59 69 33 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33
53 59 69 35 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33 35
53 59 69 41 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33 35 41
53 59 69 43
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33 35 41 43
53 59 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33 35 41 43 53
59 69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Execução:
0 16 25 26 27 33 35 41 43 53 59
69
...
Se (inicio < fim) {
meio = (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
...
O algoritmo MergeSort
 Vetor Ordenado:
0 16 25 26 27 33 35 41 43 53 59 69
O algoritmo MergeSort
principal
{
 inteiro vetor[] = {7, 6, 5, 4, 8, 22, 3, 55, 7, 99, 11, 3, 1, 88};
 inteiro tamanho;
 inteiro indice;
//Pode-se usar a função sizeof()
 tamanho  tamanho_vetor / tamanho_de_um_inteiro; 
 
 mergesort(vetor, 0, tamanho);
}
 Implementação do algoritmo MergeSort:
O algoritmo MergeSort
 Implementação do algoritmo MergeSort:
mergesort(inteiro *vetor,inteiro inicio,inteiro fim)
{
 inteiro meio;
 Se (inicio < fim) {
meio  (inicio + fim) / 2;
 mergesort(vetor, inicio, meio);
 mergesort(vetor, meio+1, fim);
 intercala(vetor, inicio, meio, fim);
}
}
O algoritmo MergeSort
 Implementação do algoritmo MergeSort:
intercala(inteiro *vetor, inteiro inicio, inteiro meio, inteiro fim)
{
 inteiro indice_inicio;
 inteiro indice_meio;
 inteiro indice_aux;
 inteiro *vetor_aux;
 indice_inicio  inicio;
 indice_meio  meio+1;
 indice_aux  0;
 vetor_aux  alocacao_memoria(vetor); 
...
... 
//Continua no slide posterior
O algoritmo MergeSort
 Implementação do algoritmo MergeSort:
enquanto(indice_inicio < meio+1 ou indice_meio < fim+1) {
 se (indice_inicio = meio+1) {
 vetor_aux[indice_aux]  vetor[indice_meio];
 indice_meio  indice_meio + 1;
 indice_aux  indice_aux + 1;
 } senao se (indice_meio = fim+1) {
 vetor_aux[indice_aux]  vetor[indice_inicio];
 indice_inicio  indice_inicio + 1;
 indice_aux  indice_aux + 1;
 } senao se (vetor[indice_inicio] <= vetor[indice_meio]) {
 vetor_aux[indice_aux]  vetor[indice_inicio];
 indice_inicio  indice_inicio + 1;indice_aux  indice_aux + 1;
 } senao {
 vetor_aux[indice_aux]  vetor[indice_meio];
 indice_meio  indice_meio + 1;
 indice_aux  indice_aux + 1;
 }
 }
 ...
 //Continua no slide posterior
O algoritmo MergeSort
 Implementação do algoritmo MergeSort:
 // copia vetor intercalado para o vetor original
 para(indice_inicio = inicio;indice_inicio <= fim;indice_inicio=indice_inicio+1)
 vetor[indice_inicio]  vetor_aux[indice_inicio-inicio];
 libera_memoria(vetor_aux);
}
Estudo da estabilidade
 O algoritmo é considerado estável, pois não há a 
possibilidade de elementos iguais mudar de 
posição no processo de ordenação
 A fase de divisão do algoritmo não altera a posição 
de nenhuma chave
 Ordenação é feita pelo algoritmo de intercalação
 A intercalação é feita verificando, sequencialmente, os 
elementos de acordo com sua posição no array
 Dessa forma, elementos com mesma chave não terão a 
sua posição relativa alterada
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	MergeSort
	Cenário
	Slide 10
	Ordenação
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84