Faculdade Latino Americana de Anápolis

Bach. Ciência da Computação 8º Período

Análise de Algoritmo II

Complexidade Algoritmo QuickSort

O QuickSort é um método de ordenação baseado em divisão e conquista. Sua abordagem consiste nos seguintes passos:

• Divisão: particiona o vetor A em dois subproblemas A1 [p,(q−1)] e A2 [(q+1),r], de forma que cada elemento de A1 seja menor ou igual a A[q], e que, da mesma forma, A[q] seja menor ou igual a cada elemento de A2;

• Conquista: os dois subproblemas A1 e A2 são ordenados recursivamente pelo QuickSort;

• Combinação: Como A1 e A2 já estão ordenados, da mesma forma A também estará ordenado.

Function QuickSort (a: vetor, p: indice, r: indice)

1. se (p < r) faça:

2. q = particao(a, p, r);

3. QuickSort (a, p, (q - 1));

4. QuickSort(a, (q + 1), r);

Function particao(a: vetor, p: indice, r: indice) --> retorna: indice

1. x = a[r];

2. i = p - 1;

3. para j = p até r - 1 faça:

4. se (a[j] <= x) faça:

5. i = i + 1;

6. trocar(a, i, j);

7. trocar(a, i + 1, r);

8. retorne i + 1;

Function trocar(a: vetor, i: indice, j: indice)

1. auxiliar = a[i];

2. a[i] = a[j];

3. a[j] = auxiliar;

A relação de recorrência extraída a partir do algoritmo acima é apresentada na equação

T(n) = T(n − 1) + O(n),

Onde O(n) é a complexidade do algoritmo de particionamento. A recorrência apresentada na equação acima faz a complexidade do QuickSort ser, no pior caso, O(n²). Mesmo assim, o caso médio do método QuickSort possui complexidade da ordem de O(n log n).

O problema do QuickSort que faz sua complexidade ser O(n²) é o algoritmo partition():

quando o vetor está ordenado ou inversamente ordenado, o método retorna ao QuickSort o valor q = 1 (a inversamente ordenado) ou q = n (a ordenado), ou seja, um particionamento totalmente desbalanceado. Para vetores randômicos a partição é mais eficiente, próxima de q = n/2, trazendo então a melhor performance ao QuickSort.

Complexidade média

O algoritmo Quicksort classifica uma lista, particionando-a, classificando suas partes e depois concatenando as partes classificadas.

A idéia básica é escolher, de alguma maneira, um pivô e particionar a lista em relação ao pivô de maneira que todo elemento de uma das partes seja menor que qualquer elemento da outra parte.

Este algoritmo classifica um vetor A em ordem não decrescente. O pivô será o maior entre os dois primeiros elementos diferentes em L, sendo zero se todos os elementos forem iguais entre si.

• O desempenho de Quicksort com entrada A envolve as seguintes contribuições:

- escolha do pivô e do algoritmo de Particionamento;

- Quicksort com a sublista da esquerda (A[ m..j - 1 ] com tamanho i, i = m-j);

- Quicksort com a sublista da direita (A[ j..p ] com tamanho n – i, n = p-m+1 e i = m-j ).

• Assim, o desempenho de Quicksort com entrada A será dado por:

onde, desemp[Pivô_Partic](A) ] é o desempenho da escolha do pivô e do algoritmo Particionamento.

• Vamos usar prob(i) para a probabilidade de o pivô ser o ( i + 1 )º elemento:

• Como o algoritmo Particionamento tem complexidade linear, temos a complexidade média c M [ Pivô_Partic](n) de ordem O( n ).

• Assim, abreviando c M [Quicksort](n) por T(n), a expressão anterior se torna:

• Agora, vamos calcular a probabilidade prob(i) de o pivô ser o ( i+1 )° elemento.

• A probabilidade de qualquer elemento (1º, 2º, 3º, …, nº) estar na primeira posição é 1/n, e a probabilidade de o segundo elemento ser menor que ele é i /

n- 1.

• Assim, a probabilidade de o pivô aparecer na primeira posição e ser o (i+1)º elemento será:

• De forma análoga, a probabilidade de o pivô estar na segunda posição e ser o ( i + 1 )º elemento será

• Logo, a probabilidade de o pivô ser o ( i + 1 )º elemento é , e

prob(i) =

• Assim, para n > 1, teremos:

• Realmente, pode-se mostrar, por indução sobre n > 1, que:

• Portanto, podemos concluir que:

c M [Quicksort](n) = O( logn ).