!
#"$%
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.
& '% ()*+,-+!%.(,// -(0(*13245
67 89:; <= 9>?@A:?@BCDE9FG H; I!J#K$9:%<
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
Junção dos elementos:
[ ] 10 [ ]
[] 8 U [ ] 16 [ ]
[] 6 U [] 12 [] 18
VXWZY\[ ]!] ]^
^
_`#aRb#_Rc#_ de ddfd(`gda db dc
L ;'B%8HC(8)@*B+M,?@N:9+8!:%C=.CD(E9,OO N(P(8*;1BCRQ3S@T
hi jklm no kpqrslqrtuvwkxy zm {!|#}$kl%n
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
2
• Pior caso = N (elementos ordenados)
~ m't%jzu(j)r*t+p,qrlk+j!l%uo.uv(wk, ((j*m1tuR3qr
!#$%
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);
}
'%()*+,+!%.(, ((*1#
¡¢ £¤¥¦ §¨ ¤©ª«¬¥ª«®¯°¤±² ³¦ ´!µ#¶$¤¥%§
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".
}
· ¦'%£³®(£)«*+©,ª«¸¥¤+£!¥%®¨.®¯(°¤,¹¹ ¸(º(£*¦1®R»3ª«¼
½¾ ¿ÀÁÂ ÃÄ ÀÅÆÇÈÁÆÇÉÊËÌÀÍÎ ÏÂ Ð!Ñ#Ò$ÀÁ%Ã
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 definido como 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 Método recursivo
Divisão complicada Divisão simples
Junção Simples Junção Complicada
Ó Â'É%¿ÏÊ(¿)Ç*É+Å,ÆÇÔÁÀ+¿!Á%ÊÄ.ÊË(ÌÀ,ÕÕ Ô(Ö(¿*Â1ÉÊØ×ÙÆÇ×