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.
Respostas
Resposta:
1. Para mesclar a matriz de classificação A e criar uma cópia para a (Matriz B).
2. Onde podemos pegar a Matriz A e encontramos na Matriz de classificação B por meio de uma pesquisa binaria, os números de inversões para estes elementos serão um a memos do que o índice de sua posição na Matriz B, logo cada numero inferior que aparecera após o primeiro elemento da Matriz A será um inversão.
Matriz:
(A) – Acumule os números de inversões para contrariar a variável (Num_inverso).
(b) – Remova a (Matriz A) e também de sua posição correspondente a (Matriz B).
Agora vamos executar novamente as etapa 2 até que não haja mais nenhum elemento para (A).
ex da execução dessa matriz:
Matriz A = (3,9,1,14,8,12,3,2,...)
onde se mesclarmos a classificação para a copia para Matriz B sendo assim:
Matriz B = (1,2,3,6,8,9,12,14,...)
Agora se 6 esta na 4ª posição na matriz B, portanto há 3 inversões.
sabemos disso pois 6 estava na primeira posição na matriz A, portanto qualquer elemento de inferior que possa aparecer depois na Matriz A teria o índice de ( j > i ) sendo que ( já que i neste caso é ≥ 1).
B: Se remover a Matriz A e também de sua posição correspondente na Matriz B.
A = (6,9,1,14,8,12,3,2)=(9,1,14,8,12,3,2)
B = (1,2,3,6,8,9,12,14)=(1,2,3,8,9,12,14).
Se executarmos novamente a partir da segunda etapa os dois nós novos A e B sendo assim:
A = 9
B = (1,2,3,8,9,12,14).
Explicação:
O número de inversões em uma matriz é a metade da distância total que os elementos devem ser movidos para classificar a matriz. Portanto, ele pode ser calculado classificando a matriz, mantendo a permutação resultante p [i] e, em seguida, calculando a soma de abs (p [i] - i/2).
Funcionamento do algoritmo
1. Mesclar a matriz de classificação A e criar uma cópia (matriz B).
2. Pegue A [1] 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 B, pois cada número inferior que aparecer após o primeiro elemento de A será uma inversão.
2.1 Acumule o número de inversões para contrariar a variável num_inversions.
2.2 Remova A [1] da matriz A e também 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.
Saiba mais sobre algoritmos em: https://brainly.com.br/tarefa/47707877
#SPJ2
