Análise de Algoritmos - A3

Prévia do material em texto

Caro(a) aluno(a), 
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 A[1 ... n ] de n números reais, um par (A[ i ], A[j]) é dito ser uma inversão se esses números estão fora de ordem, ou seja, quando i < j, temos que A[i] > A[j]. 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 O(nlog(n)), 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. 
RESPOSTA: 
1. Mesclar a matriz de classificação A e criar uma cópia (matriz B)
2. Pegue A e encontre sua posição na matriz classificada B por meio de uma pesquisa binária. O número de inversões para este elemento será um a menos que o número índice de sua posição em B, pois cada número inferior que aparecer após o primeiro elemento de A será uma inversão 
2a. Acumule o número de inversões para contrariar a variável num inverso;
2b. Remover A da matriz A e de sua posição correspondente na matriz B.
3. Execute novamente a partir da etapa 2 até que não haja mais elementos em A.
Exemplo de execução desse algoritmo:
Matriz original A = (3, 9, 1, 14, 8, 12, 3, 2)
1: Mesclar classificar e copiar para a matriz B
B = (1, 2, 3, 6, 8, 9, 12, 14)