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].

 

 

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