Atividade 03

Prévia do material em texto

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.
 
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.
 Isso leva tempo O (n log n), o que é ideal.
Para obter um melhor resultado , é utilizando o Algoritmo Merge Sort.
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 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_inversions.
2b. 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.
Aqui está um exemplo de execução desse algoritmo. 
Matriz original A = (6, 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)
2: Pegue A [1] e pesquisa binária para encontrá-lo na matriz B
A [1] = 6
B = (1, 2, 3, 6 , 8, 9, 12, 14)
6 está na 4ª posição da matriz B, portanto, há 3 inversões. Sabemos disso porque 6 estava na primeira posição na matriz A, portanto, qualquer elemento de valor inferior que apareça posteriormente na matriz A teria um índice de j> i (já que i neste caso é 1).
2.b: Remova A [1] da matriz A e também de sua posição correspondente na matriz B (os elementos em negrito são removidos).
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)
3: Execute novamente a partir da etapa 2 nos novos arrays A e B.
A [1] = 9
B = (1, 2, 3, 8, 9, 12, 14)
9 está agora na 5ª posição da matriz B, portanto, há 4 inversões. Sabemos disso porque 9 estava na primeira posição na matriz A, portanto, qualquer elemento de valor inferior que apareça subsequentemente teria um índice de j> i (já que i, nesse caso, é novamente 1). Remova A [1] da matriz A e também de sua posição correspondente na matriz B (os elementos em negrito são removidos)
A = ( 9 , 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 8, 9 , 12, 14) = (1, 2, 3, 8, 12, 14)
Continuar nessa linha nos dará o número total de inversões para a matriz A assim que o loop for concluído.
A etapa 1 (classificação por mesclagem) levaria O (n * log n) para ser executada. 
A etapa 2 seria executada n vezes e, a cada execução, faria uma pesquisa binária que leva O (log n) para um total de O (n * log n). O tempo total de execução seria, portanto, O (n * log n) + O (n * log n) = O (n * log n).
O pior tempo de execução de O (n ^ 2), quando a lista já está classificada, e o primeiro pivô é escolhido a cada rodada. O pior caso de mesclagem de classificação é O (n log n)
Estrutura em Pyton:
# O(n log n)
def count_inversion(lst):
 return merge_count_inversion(lst)[1]
def merge_count_inversion(lst):
 if len(lst) <= 1:
 return lst, 0
 middle = int( len(lst) / 2 )
 left, a = merge_count_inversion(lst[:middle])
 right, b = merge_count_inversion(lst[middle:])
 result, c = merge_count_split_inversion(left, right)
 return result, (a + b + c)
def merge_count_split_inversion(left, right):
 result = []
 count = 0
 i, j = 0, 0
 left_len = len(left)
 while i < left_len and j < len(right):
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 count += left_len - i
 j += 1
 result += left[i:]
 result += right[j:]
 return result, count 
#test code
input_array_1 = [] #0
input_array_2 = [1] #0
input_array_3 = [1, 5] #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5] #5
input_array_7 = [4, 1, 3, 2, 9, 1] #8
print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)