MergeSort Intercalação David Menotti Algoritmos e Estruturas de Dados I DECOM – UFOP Problema de Ordenação Dado um arranjo com n números naturais, ordenar estes números em ordem crescente. Entrada: 95 48 70 86 21 37 Saída: 37 48 70 86 95 © David Menotti 21 Algoritmos e Estrutura de Dados I Abordagem Dividir-para-Conquistar Método em Computação que consiste em Dividir a entrada em conjuntos menores Resolver cada instância menor de maneira recursiva Reunir as soluções parciais para compor a solução do problema original. © David Menotti Algoritmos e Estrutura de Dados I Abordagem Balanceamento Métodos de ordenação de divisão por conquista SelectSort QuickSort (pior caso?) Divisão do problema de forma balanceada MergeSort © David Menotti Algoritmos e Estrutura de Dados I Exemplo de MergeSort Entrada: 47 26 33 05 99 38 64 15 1. Divide: 47 26 33 05 99 38 64 15 2. Resolve Recursivamente: 1. Primeira metade 47 26 33 05 (Divide, Resolve recursivamente, Intercala Obtendo 05 26 33 47 ) 2. Segunda metade 99 38 64 15 (Divide, Resolve recursivamente, Intercala Obtendo 15 38 64 99 ) © David Menotti Algoritmos e Estrutura de Dados I Exemplo de MergeSort Entrada: 99 38 64 15 Resolve Recursivamente: 2. (Retorna 05 26 33 47 ) (Retorna 15 38 64 99 ) 1. 2. 2. 47 26 33 05 Intercala as soluções parciais: 05 15 26 33 38 47 64 99 © David Menotti Algoritmos e Estrutura de Dados I Algoritmo MergeSort void MergeSort(Item* A,int ini,int fim) { int meio; if (fim == ini) return; else { meio = ( ini + fim ) / 2; MergeSort(A, ini, meio ); MergeSort(A, meio+1, fim); Intercala(A, ini, meio, fim ); return; } } © David Menotti Algoritmos e Estrutura de Dados I Implementação de Intercala IntercalaAB(Item* c,Item* a,int N,Item* b,int M) { int i, j, k; for (i = 0, j = 0, k = 0; k < N+M; k++) { if ( i == N ) { c[k] = b[j++]; continue; } if ( j == M ) { c[k] = a[i++]; continue; } if ( a[i] < b[j] ) c[k] = a[i++]; else c[k] = b[j++]; } } © David Menotti Algoritmos e Estrutura de Dados I Exemplo de MergeSort 6 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 2 6 6 5 5 5 5 2 2 2 2 2 2 2 2 2 © David Menotti 8 8 5 6 6 6 6 5 5 5 5 5 5 5 5 3 5 5 8 8 8 8 8 6 6 6 6 6 6 6 6 4 10 9 12 1 10 9 12 1 10 9 12 1 10 9 12 1 9 10 12 1 9 10 1 12 1 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 8 9 10 12 5 6 7 8 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 15 7 3 13 4 11 7 15 3 13 4 11 7 15 3 13 4 11 3 7 13 15 4 11 3 7 13 15 4 11 3 7 13 15 4 11 3 7 13 15 4 11 3 4 7 11 13 14 9 10 11 12 13 14 16 16 16 16 16 16 16 16 16 16 16 16 14 14 15 15 14 14 14 14 14 14 14 14 14 14 14 14 16 16 16 16 Algoritmos e Estrutura de Dados I Implementação do MergeSort O procedimento Intercala requer o uso de um segundo arranjo, B, para receber os dados ordenados. Note que no retorno de Mergesort com um arranjo de tamanho 1, a resposta encontra-se no arranjo A (o arranjo original de entrada). No próximo nível (arranjo de comprimento 2) o resultado da intercalação estará no arranjo B. Podemos administrar este problema de duas maneiras. © David Menotti Algoritmos e Estrutura de Dados I Implementação do MergeSort Podemos administrar este problema de duas maneiras: Copiando a porção do arranjo referente ao resultado de volta para o arranjo A, ou Utilizando uma chave para indicar a “direção” dos movimentos de Intercala. © David Menotti Algoritmos e Estrutura de Dados I Complexidade do MergeSort TMergeSt(n) = 2 TMergesort(n/2) + cte n + cte Desenvolvendo TMS (n) = 2 TMS(n/2) + c n + c = 2 [ 2 TMS(n/4) + c n/2 + c ] + c n + c = 4 TMS(n/4) + 2c n + 3c = 4 [ 2 TMS(n/8) + c n/4 + c ] + 2c n + 3c = 8 TMS(n/8) + 3c n + 7c = ... TMS (n) = 2i TMS(n/2i) + i c n + (2i-1) c © David Menotti Algoritmos e Estrutura de Dados I Complexidade do MergeSort Temos que TMS(n) = 2i TMS(n/2i) + i c n + (2i-1) c. Tem-se que TMS(1) = 1 e (n/2i) = 1 (i = log2n). TMS(n) = 2log2n cte + (log2n) c n + (2log2n - 1) c = n cte + c n log2n + c (n-1) = c n log2n + (cte+c) n - c TMS(n) = O(n log2n) © David Menotti Algoritmos e Estrutura de Dados I MergeSort Vantagens Como HeapSort, MergeSort é O(n log n) Indicado para aplicações que exigem restrição de tempo (executa sempre em um determinado tempo para um dado n) Passível de ser transformado em estável Implementação de intercala Fácil Implementação Desvantagens Utiliza memória auxiliar – O(n) Na prática mais lento que HeapSort © David Menotti Algoritmos e Estrutura de Dados I