GRA0559 ANÁLISE DE ALGORITMOS GR0075211 - 202110.ead-14790.01 ATIVIDADE 4

Prévia do material em texto

ATIVIDADE 02
O entendimento dos algoritmos de ordenação apresentados n esta unidade é essencial 
para o desenvolvimento das habilidades necessárias p ara projetar soluções 
computacionais em cenários variados. De fato, saber emprega r 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 sistem as 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 o rdem, 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 al goritmo de
complexidade O(nlog(n)), tanto no melhor como no pior casos, pode ser pr ojetado para
contar o número de inversões existent es 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 .
Funcionamento do algoritmo
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 binaria. 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 da matriz A e também de sua posição correspondente na matriz B
3. execute novamente a partir da etapa 2 ate que não haja mais elementos em A.
Aqui está um 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)
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 da matriz A e também da 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)
3: execute novamente a partir da etapa 2 nos novos A e B
A = 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, remova A da matriz e também de sua posição correspondente na matriz B 
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 numero total de inversões para a matriz A assim que o loop for concluído.
A etapa 1 levaria O (n * log n) para ser executada.
A etapa 2 seria executada n vezes e, cada execução faria uma pesquisa binaria 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)