Análise e Projeto de Algoritmos: Ordenação MergeSort

Análise e Projeto de Algoritmos Márcia Cappelle e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás Ciência da Computação 2021 INFUFG APA 20202 M Cappelle H Coelho 1 1 de 804 Ordenação MergeSort Divisão e conquista O método de ordenação Mergesort utiliza a técnica de projeto de algoritmos chamada divisão e conquista que consiste basicamente em Dividir o problema em um determinado número de subproblemas Conquistar os subproblemas resolvendoos recursivamente Se forem pequenos o bastante diretamente Combinar as soluções dadas aos subproblemas a m de formar a solução para o problema original INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 274 388 de 804 Ordenação MergeSort Funcionamento do Mergesort Dividir Divide a sequência de elementos em duas de tamanho aproximadamente n2 Conquistar Classica as duas sequências recursivamente usando a intercalação Combinar Faz a intercalação das duas sequências ordenadas para obter uma única sequência ordenada INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 275 388 de 804 Ordenação MergeSort MergeSortA ini fim Entrada vetor Ainifim inteiros não negativos ini e fim Saída vetor Ainifim ordenado 1 se ini fim então 2 p inifim 2 3 MergeSortA ini p 4 MergeSortA p 1 fim 5 IntercalaA p ini fim INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 276 388 de 804 Ordenação Mergesort IntercalaA p ini fim Entrada vetores crescentes Ainip e Ap 1fim e inteiros não negativos p ini e fim Saída vetor crescente Ainifim 1 i ini j p 1 k 1 2 enquanto i p e j fim faça 3 se Ai Aj então 4 Bk Ai 5 i i 1 6 senão 7 Bk Aj 8 j j 1 9 k k 1 10 enquanto i p faça Bk Ai i i 1 k k 1 11 enquanto j fim faça Bk Aj j j 1 k k 1 12 Ainifim B1k 1 INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 277 388 de 804 Ordenação MergeSort Correção e complexidade do Intercala Loop invariante para o laço da linha 2 1 B1k 1 contém os k 1 menores elementos de Ainip e Ap 1fim em sequência ordenada 2 se i p Ai Bk 1 e se j fim Aj Bk 1 Complexidade do Intercala Θn No pior caso quantas vezes a comparação da linha 3 é vericada INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 278 388 de 804 MergeSort Relacdo de recorréncia e1 se n1 rm rig T2 0 L sTslOn se n A funcdo Tn nado mostra de forma clara o comportamento assintotico Conveniéncia da funcdo Tn escrita na forma explicita ou forma fechada eS 9 INFUFG APA 20202 M Cappelle H Coelho Analise Alg Recursivos 279 388 de 804 MergeSort Relacdo de recorréncia Versdo simplificada 1 se nl Tn M rEg ertyyen a nol P Caso particular em que n é poténcia de 2 1 see n1 Tn o oe se nlen2 para k1 o8 9 INFUFG APA 20202 M Cappelle H Coelho Analise Alg Recursivos 280 388 de 804 Obtendo uma fórmula fechada para a recorrência Método iterativo Abrir repetidas vezes a recorrência até conseguir identicar um padrão na mesma Considere Tn 2T n 2 n Tn n 2T n 2 n 2 n 2 2T n 4 n 2n 2 4T n 4 n 2n 2 4n 4 8T n 8 n 2n 2 4n 4 8n 8 2iT n 2i Iteração até n 2i 1 ou seja i lg n INFUFG APA 20202 M Cappelle H Coelho Análise Alg Recursivos 281 388 de 804 Obtendo uma formula fechada para a recorréncia Método iterativo Abrir repetidas vezes a recorréncia até conseguir identificar um padraéo na mesma Considere Tn 2T5 n Tn ne 46 482 442TS a j0 Ign1 x 7 B271 j0 Ign1 n 142871 j0 nignn Onlgn eS 9 INFUFG APA 20202 M Cappelle H Coelho Analise Alg Recursivos 282 388 de 804 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20202 M Cappelle H Coelho Bibliograa 804 804 de 804