Aulas sobre Quicksort

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
QUICKSORT
Katia S. Guimarães
katia@cin.ufpe.br
katia@cin.ufpe.br
*
*
*
Uma outra abordagem 
Dividir-para-conquistar?
Vimos que o Mergesort usava a abordagem dividir-para-conquistar, porém fazia a divisão de forma trivial, levando a muito trabalho na fase de conquistar.
Será que poderíamos encontrar um esquema onde a divisão fosse feita com mais cuidado, de forma a tornar a conquista mais rápida?
katia@cin.ufpe.br
*
*
*
Uma outra abordagem 
Dividir-para-conquistar
Vamos procurar dividir o array em duas partes, de forma que:
 - Os elementos y, menores que um certo elemento x fiquem todos à esquerda de x, e 
 - Os elementos z, maiores do que x fiquem todos à direita de x.
 y  x x x < z 
katia@cin.ufpe.br
*
*
*
Uma outra abordagem 
Dividir-para-conquistar
Ficam duas questões:
 1- Será que isso agiliza a etapa do conquistar?
 2- Quanto custa fazer uma divisão tão sofisticada? 
Se dividirmos o array de acordo com esta regra, na fase de conquistar (após o retorno das chamadas recursivas) o arquivo estará ordenado!
katia@cin.ufpe.br
*
*
*
Quanto Custa Dividir?
Como fazer uma divisão tão sofisticada?
Vamos começar definindo quem será o “pivô” x.
Se nenhuma distribuição dos elementos é conhecida, então um elemento é tão bom como outro qualquer no array.
Tomaremos pivô  x[1] 
katia@cin.ufpe.br
*
*
*
Quanto Custa Dividir?
Em seguida, vamos começar a inspecionar o array pela esquerda, prosseguindo enquanto o elemento y sendo inspecionado for  x: 
 i  left;
 enquanto array[i]  x faça 
 i  i + 1
x y  x z 
left
right
i    
katia@cin.ufpe.br
*
*
*
Onde devemos colocar o elemento z?
Como z > x, ele deve ser colocado numa posição mais à direita do array. Mas onde?
Talvez na última posição do array?
x y  x z 
left
right
i     

z?
katia@cin.ufpe.br
*
*
*
Onde devemos colocar o elemento z?
Observe que na última posição do array pode haver um outro elemento t com t > x. 
Se colocarmos z ali, estaremos fazendo trabalho inútil, pois t já está no lugar correto.
Então onde colocaremos z? 
katia@cin.ufpe.br
*
*
*
Onde será um bom lugar para z?
Vamos começar a inspecionar o array pela direita, prosseguindo enquanto o elemento t sendo inspecionado for > x: 
 j  right;
 enquanto array[j] > x faça 
 j  j - 1
x y  x z 
left
right
i
   j
x  y
 t

katia@cin.ufpe.br
*
*
*
Situação conveniente
Temos z = array[i] > x e t = array[j]  x 
 Se os trocarmos, teremos reduzido a nossa
 tarefa a um array bem menor que o original.
x y  x z 
left
right
i
t
 j
x  y
x y  x t 
z
x  y
x y  x 
x  y
katia@cin.ufpe.br
*
*
*
Custo de Particionar?
Como varremos o array comparando cada elemento com o pivô (eventualmente trocando os elementos de posição), o custo é  (n).
x y  x z 
left
right
i
t
 j
x  y
x y  x t 
z
x  y
x y  x 
x  y
katia@cin.ufpe.br
*
*
*
Algoritmo Particiona
Algoritmo Particiona (A, left, right)
 i  left; j  right; pivô  A[left];
 while i < j do {
 while A[i]  pivô do i  i + 1; 
 while A[j] > pivô do j  j - 1; 
 if i < j then switch (A[i], A[j])
 }
 switch (A[left], A[j])
 retorne (j)
katia@cin.ufpe.br
*
*
*
Algoritmo Quicksort
Algoritmo Quicksort (A, left, right)
 if left < right then
 { split  Particiona (A, left , right)
 Quicksort (A, left, split -1)
 Quicksort (A, split + 1, right)
 }
 retorne ( )
katia@cin.ufpe.br
*
*
*
Considerações de Implementação
Quando a quantidade de elementos é pequena, é melhor usar um outro algoritmo na chamada recursiva.
Na verdade, quando n é pequeno, quanto mais simples melhor
katia@cin.ufpe.br
*
*
*
Considerações de Implementação
Como a escolha do pivô é crucial para um bom desempenho do algoritmo, as implementações usam métodos mais sofisticados para a sua escolha, sendo os mais populares:
1. Mediana ( A[left], A[(right+left) / 2], A[right] ) 
2. Aleatório (left..right)
katia@cin.ufpe.br
*
*
*
Custo de QuickSort - Caso Desfavorável
 Se a posição do pivô no array ordenado está sempre 
 ou muito próximo do início ou muito próximo do final,
 então o tempo de execução de Quicksort é alto.
Por exemplo, se o array de entrada está ordenado, 
o pivô é sempre o menor elemento da seqüência então
    A primeira partição gasta (n-1) comparações e 
 deixa n-1 chaves por serem ordenadas. 
 Q(n) = (n–1) + (n–2) + (n–3) + ... + 1 
 = n (n –1) / 2 = (n2)
katia@cin.ufpe.br
*
*
*
Custo de QuickSort - Caso Favorável
Designaremos por Q(n) o número de comparações de chaves que Quicksort faz para uma entrada de tamanho n. 
Se o pivô sempre particionasse as chaves em partes iguais, então o número de comparações seria aproximadamente: 
 (1 * n) + (2 * n/2) + (4 * n/4) + (8 * n/8) + ... + (n * 1)
E a relação de recorrência seria:
  Q(n) = 2 * Q(n/2) + O(n) , Q(1) = 1
Neste caso, já sabemos (Mergesort) que Q(n) = (n log n).
katia@cin.ufpe.br