Quick Sort

O Quick Sort é um dos método mais rápidos de ordenação, apesar de às vezes partições desequilibradas poderem conduzir a uma ordenação lenta. Esse método de ordenação utiliza a técnica divide and conquer (dividir o problema inicial em dois subproblemas e resolver um problema menor utilizando a recursividade)

Este método baseia-se na divisão da tabela em duas sub-tabelas, dependendo de um elemento chamado pivô, normalmente o 1º elemento da tabela. Uma das sub-tabelas contém os elementos menores que o pivô enquanto a outra contém os maiores. O pivô é colocado entre ambas, ficando na posição correcta. As duas sub-tabelas são ordenadas de forma idêntica, até que se chegue à tabela com um só elemento.

Complexidade: caso médio O(N * log N)

Esse método de ordenação divide-se em vários passos:

· Escolher para pivô o primeiro elemento da tabela (p=x[1])

· Se os elementos de x forem rearranjados de forma a que o pivô (p) sejam colocados na posição j e sejam respeitadas as seguintes condições:

1. todos os elementos entre as posições 1 e j-1 são menores ou iguais que o pivô (p)

2. todos os elementos entre as posições j+1 e n são maiores que o pivô (p)

Então p permanecerá na posição j no final do ordenamento.

· Se este processo for repetido para as sub-tabelas x[1] a x[j-1] e x[j+1] a x[n] e para todas as sub-tabelas criadas nas iterações seguintes obteremos no final uma tabela ordenada.

Portanto a parte mais difícil deste método é o procedimento parte que divide a tabela em 2 sub-tabelas dependendo do pivô.

Algoritmo de Ordenação

1. Caso básico: Se o número de elementos a ordenar for 0 ou 1 então terminar

2. Seleccionar o elemento Pivô “P”: Escolhendo um elemento qualquer entre os elementos a ordenar

3. Processo de partição: Dividir os elementos em 2 subconjuntos disjuntivos na qual:

m= (x Î vector - (P) | x £ P) //elementos inferiores ao pivô

M= (x Î vector - (P) | x > P) //elementos superiores ao pivô

4. Método recursivo: Ordenar os subconjuntos esquerdo e direito, usando o mesmo método recursivamente.

Algoritmo de Escolha de Pivô

· Método Simples: Usar sempre o primeiro elemento da parte do array/vector que está sendo ordenado.

· Método Melhor: Olhar para três elementos diferentes, e usar o elemento médio entre os três.

Algoritmo de Partição

O procedimento de partição deve reorganizar os elementos de forma a que:

1. Escolha do pivô: Considere p=a[lim_inferior] como o elemento pivô

· Usa-se o primeiro elemento para facilitar a implementação.

2. Dois ponteiros alto e baixo são inicializados como os limites superior e inferior do array/vector a ordenar

· Em qualquer ponto de execução, todos os elementos acima de alto é maior do que x e todo o elemento abaixo de baixo é menor do que x.

3. Os dois ponteiros alto e baixo são movidos um em direcção ao outro da seguinte forma:

· Incrementa baixo em uma posição enquanto que a[baixo] £ p.

· Decremente alto em uma posição enquanto que a[alto] > p.

· Se alto > baixo , troque a[baixo] por a[alto].

O processo é repetido até que a condição descrita mais acima falhe (quando alto <= baixo ). Neste ponto a[alto]será trocado por a[lim_Inferior],cuja posição final era procurada, e alto é retornado em i.

Implementação:

Ÿ Divisão (procedimento) – divide a lista em 2; L1 conterá todos os elementos menores que o pivô e L2 todos os elementos que forem maiores, L0 vai conter um só elemento que é o pivô

Ÿ Quick Sort

Em pseudocódigo:

P dividir (l, l0, l1, l2, pivo)

Se é_vazia (l)

Então l0=NULL

l1=NULL

l2=NULL

Senão dividir(l, lo, l1, l2, pivo)

Se cabeça(l) < pivo

Então l1=criar (cabeça(l), l1)

Senão Se cabeça (l) > pivo

Então l2=criar (cabeça(l), l2)

Senão l0=criar (cabeça(l), l0)

Quick_Sort (l) à lista

Se é_vazia(l)

Então devolver NULL

Senão Se é_vazia(l)

Então devolver l

Senão dividir (l, l0, l1, l2, cabeça(l))

devolver concatenar (quick_sort(l1), concatenar(l0, quick_sort(l2)))

Exemplos:

Implementação em C++

Vamos considerar um Array de números inteiros, também vamos considerar que a variável tam, do tipo numérica inteira, com o tamanho de nosso Array.

void quick(int Q[50], int inicio, int fim)
{
int meio;
comparacoes[4]++;
if (inicio<fim)
{
   atribuicoes[4]++;
   meio = particiona(Q, inicio, fim);
   quick(Q, inicio, meio-1);
   quick(Q, meio+1, fim);
  }
}

int particiona(int Q[50], int inicio, int fim)
{
int pivo, ultbaixo, temp, i;
atribuicoes[4]++;
pivo = Q[inicio];
ultbaixo = inicio;

for(i=inicio+1; i<=fim; i++)
{
comparacoes[4]++;
if (Q[i]<=pivo)
{
    ultbaixo++;
   atribuicoes[4]+=3;
    temp = Q[i];
    Q[i] = Q[ultbaixo];
    Q[ultbaixo] = temp;
   }
}

atribuicoes[4]+=3;
temp = Q[inicio];
Q[inicio] = Q[ultbaixo];
Q[ultbaixo] = temp;
return(ultbaixo);
}

Exercícios:

1 - Considere o caso onde todos os pivôs do quick sort dividem a lista numa lista vazia e numa lista que contém todos os elementos maiores que o pivô. Este caso degenerado do quick sort é equivalente a outro algoritmo de ordenação?

Solução - Sim é a ordenação por inserção, onde encontra iterativamente os elementos menores dos restantes que ainda não estão ordenados e coloca-os no início da lista.

2 – Explica como o método do pivô sofisticado pode ajudar na eficiência do algoritmo do quick sort?

Solução – O quick sort executa o algoritmo escolhendo o método do melhor pivô. Se todo o pivô dividir a lista, aproximadamente, ao meio, a ordenação corre numa complexidade de: O(N * log(N) ). Este método é eficiente se a escolha do pivô um elemento cujo valor seja médio relativamente aos restantes.

3 –Explique porque é que a seguinte lista é pouco eficiente no método de ordenação do quick sort.

Lista: (9, 8, 7, 6, 5, 4, 3, 2, 1)

Solução – Visto que o algoritmo escolhe o primeiro elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada (decrescentemente).

Links:

Ÿ Para a animação do quick sort

http://utopia.poly.edu/~kshanm01/algorithm/quick_sort_simulation.html