Analise de Algoritimos - A3

Prévia do material em texto

Para contar o número de inversões em um vetor de n números reais, podemos utilizar o
algoritmo de merge sort, que possui complexidade O(nlog(n)) tanto no melhor caso quanto
no pior caso.
O merge sort consiste em dividir o vetor em dois subvetores de tamanhos iguais (ou quase
iguais), ordenar recursivamente cada subvetor e, em seguida, combinar os subvetores
ordenados em um único vetor ordenado.
Ao combinar os subvetores, podemos contar o número de inversões de forma eficiente.
Seja L o subvetor esquerdo e R o subvetor direito. Quando combinamos os subvetores, se
L[i] é maior do que R[j], então todos os elementos a partir de L[i] até L[m], onde m é o
tamanho do subvetor esquerdo, formam uma inversão com R[j]. Isso ocorre porque, como L
e R estão ordenados, todos os elementos de L a partir de L[i] serão maiores do que R[j].
O pseudocódigo do algoritmo de merge sort para contar o número de inversões é o
seguinte:
função mergeSort(vetor, inicio, fim):
se inicio < fim então
meio = (inicio + fim) / 2
mergeSort(vetor, inicio, meio)
mergeSort(vetor, meio+1, fim)
merge(vetor, inicio, meio, fim)
função merge(vetor, inicio, meio, fim):
n1 = meio - inicio + 1
n2 = fim - meio
// cria os subvetores L e R
para i de 1 até n1 faça
L[i] = vetor[inicio+i-1]
para j de 1 até n2 faça
R[j] = vetor[meio+j]
// combina os subvetores L e R em um único vetor ordenado
i = 1
j = 1
k = inicio
inversoes = 0
enquanto i <= n1 e j <= n2 faça
se L[i] <= R[j] então
vetor[k] = L[i]
i = i + 1
senão
vetor[k] = R[j]
j = j + 1
inversoes = inversoes + n1 - i + 1
k = k + 1
enquanto i <= n1 faça
vetor[k] = L[i]
i = i + 1
k = k + 1
enquanto j <= n2 faça
vetor[k] = R[j]
j = j + 1
k = k + 1
retorna inversoes
No algoritmo acima, a função mergeSort ordena recursivamente o vetor usando a função
merge para combinar os subvetores ordenados. A variável inversoes conta o número de
inversões na combinação dos subvetores.
No final da execução do merge sort, a variável inversoes contém o número total de
inversões no vetor. O algoritmo tem complexidade O(nlog(n)) tanto no melhor caso quanto
no pior caso.