Aula 04 - Fusão ou Intercalação (MergeSort)

Prévia do material em texto

Baseia-se na estratégia de DIVIDIR PARA CONQUISTAR e possui complexidade (O(log2n)).
Divisão: Divide o vetor original em dois outros tamanhos menores recursivamente, até obter vetores 
de tamanho 1
Junção: Intercala os elementos dos dois vetores ordenados para obter a ordenação total.
Divisão
Conquista
Combina
Algoritmo
Caso o tamanho do vetor seja maior que 1 
1. Divida o vetor no meio 
2. Ordene a primeira metade recursivamente 
3. Ordene a segunda metade recursivamente 
4. Intercale as duas metades 
MergeSort (V, inicio, fim)
 if (inicio < fim)
 {
 meio = (inicio + fim)/2;
 Mergesort(V, inicio, meio);
 Mergesort(V, meio+1, fim);
 Merge(V, inicio, meio, fim);
 }
 else 
 {
 return;
 }
0 5 1 3 2 1 3 2 4 4
mergeSort (V, 0, 4) →meio = 2 (1) (2) →Merge (V, 0, 2, 4) → 1 2 3 4 5
mergeSort (V, 0, 2) →meio = 1 (1) (2) →Merge (V, 0, 1, 2) → 1 3 5 2 4 
Semana 05 - Aula 04 - Fusão ou Intercalação (MergeSort)
quarta-feira, 26 de março de 2014 21:10
 Página 1 de COM112 - Algoritmo e Estrutura de Dados II 
mergeSort (V, 0, 2) →meio = 1 (1) (2) →Merge (V, 0, 1, 2) → 1 3 5 2 4 
mergeSort (V, 0, 1) →meio = 0 (1) (2) (3) →Merge (V, 0, 0, 1) → 3 5 1 2 4
mergeSort (V, 0, 0) → return 5 
mergeSort (V, 1, 1) → return 3
mergeSort (V, 2, 2) → return 1
mergeSort (V, 3, 4) →meio = 3 (1) (2) →Merge (V, 3, 3, 4) → 1 3 5 2 4
mergeSort (V, 3, 3) → return 2 
mergeSort (V 4, 4) → return 4
 Página 2 de COM112 - Algoritmo e Estrutura de Dados II