quicksort

Prévia do material em texto

��� ������� 	�
�����
�������
�������������ff�fiffifl�� �! #"$���%	
&
�'�%��fl��(�)�*�+�,
���-����+�!�%��
.���(���,/�/ -(0(�*�1���324
���5
 
5. Quick Sort 
 
5.1. Ideia Básica 
 
O método de ordenação quick sort utiliza a técnica divide and conquer (dividir o 
problema em dois subproblemas e resolver um problema menor utilizando recursividade), 
e é um dos métodos mais rápidos de ordenação. 
A principal característica deste método consiste na escolha de um elemento para pivô 
(elemento já ordenado) e dividir os elementos a ordenar em dois subconjuntos na qual no 
primeiro subconjunto todos os elementos são menores ou iguais ao valor de pivô, e no 
segundo subconjunto todos os elementos são maiores ou igual ao valor de pivô. Os dois 
subconjunto são ordenados de forma recursiva. Quicksort é mais rápido em média, mas às 
vezes partições desequilibradas podem conduzir a uma ordenação muito lenta. 
 
5.2. Métod 
 
O método de ordenação quick sort, selecciona inicialmente um dos elementos do 
conjunto a ordenar para ser o elemento pivô (elemento já ordenado), efectuado de seguida 
uma subdivisão do conjunto inicial em dois subconjunto, na qual o primeiro subconjunto 
contém todos os elementos menor que o elemento pivô, e o segundo subconjunto todos os 
elementos maiores que o pivô. Os dois subconjuntos são ordenados através da invocação 
recursiva da função de ordenação. O processo pára quando o subconjunto a ordenar 
contém zero ou um elementos. 
 
Considere-se que se pretende ordenar o seguinte conjunto de elementos. 
 
10 8 6 2 16 4 18 11 14 12 
 
Apresenta-se de seguida uma esquema como os elementos são ordenados utilizando este 
método. 
 
 
6�7 8�9�:�; <�=�9�>�?�@�A�:�?�@�B�C�D�E�9�F�GffiH�; I!J#K$9�:%<
L
;'B%8�H�C(8)@*B+M,?�@�N�:�9+8!:%C�=.C�D(E�9,O�O N(P(8*;1B�CRQ3S�@�T
 
Vista em árvore: 
 
10 8 6 2 16 4 18 11 14 12 
 
 
8 6 2 4 10 16 18 11 14 12 
 
 
6 2 4 8 12 11 14 16 18 
 
 
2 4 6 11 12 14 18 
 
 
 
2 4 11 14 
 
 
4 
 
Junção dos elementos: 
[ ] 10 [ ] 
 
 
[ ] 8 U [ ] 16 [ ] 
 
 
[ ] 6 U [ ] 12 [ ] 18 
 
 
VXWZY\[ ]!] ]�^
^
_�`#aRb#_Rc#_ d�e d�dfd(`gd�a d�b d�c
 
h�i j�k�l�m n�o�k�p�q�r�s�l�q�r�t�u�v�w�k�x�yffiz�m {!|#}$k�l%n
~
m't%j�z�u(j)r*t+p,q�r��l�k+j!l%u�o.u�v(w�k,€�€ ((j*m1t�uR‚3q�r�ƒ
 
5.3. Algoritmo 
5.3.1. Algoritmo de Ordenação 
 
1. Caso Básico: Se o nú ero 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 disjuntos 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. 
 
5.3.2. Algoritmo de Escolha de Pivô 
 
• Método Simples:
 Sempre use o primeiro elemento da parte do array/vector que está 
sendo ordenada. 
• Método Melhor:
 Olhe para três elementos diferentes, e use o elemento médio entre os 
três. 
 
5.3.3. Algoritmo de Partição 
 
O procedimento de partição deve reorganizar os elementos por forma a que: 
1. Escolha do Pivô: Considere p=a[lim_inf] 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 d
array/vetor a ordenar 
• Em qualquer ponto da execução, todo elemento acima de alto é maior do que x e 
todo 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: 
1. Incremente baixo em uma posição enquanto que a[baixo] <= p. 
2. Decremente alto em uma posição enquanto que a[alto] > p. 
3. Se a alto > baixo , troque a[baixo] por a[alto]. 
4. O processo é repetido até que a condição descrita em 3. falhe (quando 
alto <= baixo ). Neste pont a[alto]será trocado por a[limInf],cuja posição final era 
procurada, e alto é retornado em i. 
 
5.4. Eficiência 
 
Tempos de Ordenação (sendo N o número de elementos a ordenar) 
• Melhor caso =
 N log N 
• Média = N log N 
• Pior caso = N2 (elementos ordenados) 
 
„�… †�‡�ˆ�‰ Ł�‹�‡�Œ��Ž��ˆ��Ž��‘�’�“�‡�”�•ffi–�‰ —!˜#™$‡�ˆ%Ł
š
‰'%†�–�‘(†)Ž*+Œ,�Ž�›�ˆ�‡+†!ˆ%‘�‹.‘�’(“�‡,œ�œ ›((†*‰1�‘#žŸ�Ž� 
 
5.5. Implementação em C++ 
 
void quicksort(int v[], int lim_inf, int lim_sup) 
// Array de numeros inteiros, Limite inferior e Limite Superior 
{ int i; 
 if (lim_sup > lim_inf esq) 
 { i = particao(lim_inf esq, lim_sup); 
 quicksort(lim_inf esq, i-1); 
 quicksort(i+1, lim_sup); 
 } 
} 
 
• Os parâmetros lim_inf e lim_sup delimitam o subconjunto de elementos a ordenar de 
entre todos os elementos a ordenar. 
• A invocação inicial da função de ordenação, pode ser efectuada da seguinte forma: 
quicksort(v, 1, N); 
• O ponto crucial do algoritmo de ordenação é o algoritmo de partição. 
 
int particao(int v[], int lim_inf, int lim_sup) 
{ 
 if (lim_inf < lim_sup) 
 { 
 int pivo = v[lim_inf]; // seleccao do pivo pelo metodo simples 
 int esq = lim_inf; // Apontador esquerdo (do limite inferior) 
 int dir = lim_sup; // Apontador direito (do limite superior) 
 esq++; // avancar o limite inferior (pivo fica na 1. posicao) 
 for(;esq < dir;) 
 { 
 while (v[esq] < pivo) 
 esq++; // avancar apontador por cada elemento que se encontra 
 // no lado correcto 
 while (v[dir] > pivo) 
 dir--; // avancar apontador por cada elemento que se encontra 
 // no lado correcto 
 if (esq < dir) // se apontadores ainda nao estao trocados 
 trocar(v, esq, dir); // trocar os valores 
 } 
 if (v[lim_inf] > v[dir]) 
 trocar(v, lim_inf, dir); // Colocar o pivo na posicao correcta 
 return(dir); 
 } 
 return(-1); 
} 
¡�¢ £�¤�¥�¦ §�¨�¤�©�ª�«�¬�¥�ª�«�­�®�¯�°�¤�±�²ffi³�¦ ´!µ#¶$¤�¥%§
·
¦'­%£�³�®(£)«*­+©,ª�«�¸�¥�¤+£!¥%®�¨.®�¯(°�¤,¹�¹ ¸(º(£*¦1­�®R»3ª�«�¼
 
5.6. Exemplo 
 
data 
10 8 6 2 16 4 18 11 14 12 
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
 
1º passo de ordenação: 
Pivô: dados[0] = 10 
Dividir o array em 2 subconjuntos 
8 6 2 4 10 16 18 11 14 12 
 
2º passo de ordenação: 
Pivô: dados[0] = 8 
Dividir o array em 2 subconjuntos 
6 2 4 8 
 
3º passo de ordenação: 
Pivô: dados[0] = 6 
Dividir o array em 2 subconjuntos 
2 4 6 
 
 
5.7. QSORT definida na STL 
 
#include <algorithm> 
 
exemplo 1: 
int A[] = {1, 4, 2, 8, 5, 7}; 
const int N = sizeof(A) / sizeof(int); 
sort(A, A + N); 
 
exemplo 2:
 
inline bool funcao_menor(char c1, char c2) 
{ return tolower(c1) < tolower(c2); } 
 
int main() 
{ 
 char A[] = "fdBeACFDbEac"; 
 const int N = sizeof(A) - 1; 
 
stable_sort(A, A+N, lt_nocase); 
 printf("%s\n", A); 
 // The printed result is ""AaBbCcdDeEfF". 
} 
 
 
½�¾ ¿�À�Á� Ã�Ä�À�Å�Æ�Ç�È�Á�Æ�Ç�É�Ê�Ë�Ì�À�Í�ÎffiÏ� Ð!Ñ#Ò$À�Á%Ã
Ó
Â'É%¿�Ï�Ê(¿)Ç*É+Å,Æ�Ç�Ô�Á�À+¿!Á%Ê�Ä.Ê�Ë(Ì�À,Õ�Õ Ô(Ö(¿*Â1É�ÊØ×ÙÆ�Ç�×
 
A função qsort da biblioteca standard de C 
 
Para utilizar esta função é necessário efectuar a inclusão da bibliote ca: 
#include <stdlib.h> 
 
contendo o seguinte protótipo: 
void qsort(void *firstElem, size_t nElem, size_t sizeElem, 
int (*cmpElem) (const void *Elem1, const void *Elem2)); 
 
na qual os seus argumentos são: 
1º - apontador para o 1º elemento do array a ordenar 
 (o tipo void * é um apontador genérico) 
2º - número de elementos existentes no array a ordenar 
 (o tipo size_t está normalmente definidocomo inteiro sem sinal 
3º - nº de bytes ocupado por cada elemento do arra 
4º - apontador para função que rece e dois apontadores para elementos do array, e 
retorna um valor <0, 0 ou >0, conforme o 1º elemento é menor, igual ou maior do que 
o 2º element 
 
5.8. Resumo 
 
• Método de ordenação extremamente rápido. 
• Algoritmo recursivo baseado na técnica divide and conquer! 
• Para evitar o pior caso procure seleccionar u bom pivô, desta forma utilize sempre o 
elemento médio entre três candidatos. 
• O espaço de memória exigido por cada chamada de QuickSort, sem contar com chamadas 
recursivas, é independente do tamanho (n) do arra 
• O espaço de memória total exigido pela chamada de QuickSort, incluindo as chamadas 
recursivas, é pois proporcional à profundidade de recursão 
 
 
5.9. Comparação de Métodos 
 
QuickSort MergeSort 
Método recursivo 
Divisão complicada 
Junção Simples 
Método recursivo 
Divisão simples 
Junção Complicada