Avaliação 3- Analise de Algoritmo

O entendimento dos algoritmos de ordenação apresentados nesta unidade é essencial para o desenvolvimento das habilidades necessárias para projetar soluções computacionais em cenários variados De fato saber empregar um algoritmo já conhecido para modelar um dado problema pode agregar eficiência e precisão ao processo de obtenção de uma resposta Um recurso muito utilizado em vários sistemas e bibliotecas computacionais é o de inversão Para um dado vetor A1 n de n números reais um par A i Aj é dito ser uma inversão se esses números estão fora de ordem ou seja quando i j temos que Ai Aj Por exemplo um vetor com os elementos 1 3 5 2 4 6 Tem as seguintes inversões 3 2 5 2 e 5 4 Proposta Considerando o recurso de inversão apresentado descreva como um algoritmo de complexidade Onlogn tanto no melhor como no pior casos pode ser projetado para contar o número de inversões existentes em um vetor de n números reais Tome como base os pseudocódigos apresentados na unidade Submeta o arquivo de sua resposta para avaliação docente Para a contagem de inversões em um Array pode ser utilizado o algoritmo de ordenação MergeSort pois ele pega duas partes ordenadas e compara índice a índice Cada elemento da parte da esquerda deve ser menor ou igual a cada elemento da parte da direita Seja A o array da esquerda e B o array da direita e que ai bj isso implica que todos os elementos à direita de ai são maiores que bj pois o vetor está ordenado ou seja bj está invertido com n2 i 1 elementos Algoritmo MergeSort Entrada Um array arr um array temp e dois inteiros left right indicando os limites da partição Saída um inteiro que representa as inversões da partição mid 0 inv 0 Se right left mid right left 2 inv inv mergeSortarr temp left mid inv inv mergeSortarr temp mid 1 right inv inv mergearr temp left mid 1 right Fim Se retorna inv Algoritmo merge Entrada Um array arr um array temp três inteiros left mid e right Saída o número de inversões inv inv 0 i left j mid k left Enquanto i mid 1 e j right Se arri arrj tempk arri k k 1 i i 1 Senao tempk arrj k k 1 j j 1 inv inv mid i Fim Se Fim Enquanto Enquanto i mid 1 tempk arri k k 1 i i 1 Fim Enquanto Enquanto j right tempk arrj k k 1 j j 1 Fim Enquanto Para i left até right faça arri tempi Fim Para retorna inv