Método Quicksort

O método Quicksort tem esse nome por ser um método que é mais rápido ordenar dois vetores com n/2 elementos cada um,  do que um com n elementos (conceito dividir para conquistar).  Além da versão recursiva, existe também a versão iterativa do Quicksort.

Funcionamento

O primeiro passo é escolher o pivô. Uma vez escolhido o pivô, os elementos do vetor são movimentados de forma que o subvetor à esquerda do pivô contenha somente os elementos cujo valor é menor que o valor do pivô e o subvetor da direita contenha valores maiores que o valor do pivô. O procedimento é repetido até que o vetor esteja ordenado.

O método quicksort é um método recursivo. Existem dois tipos de complexidade: Complexidade de Tempo e Complexidade de Espaço.
Complexidade de Tempo θ(n lg₂ n) no melhor caso e θ(n) no caso médio e θ(n²) no pior caso;
Complexidade de espaço: θ(lg₂ n) no melhor caso e no caso médio e θ(lg₂ n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n²) no pior caso.

Abaixo um exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.

a) Pivô é escolhido no meio do vetor. O elemento é colocado numa variável auxiliar trab;
b) São iniciados dois ponteiros i e j;
c) O vetor é percorrido a partir da esquerda até que se encontre um V[i] ≥ trab (i é incrementado no processo);
d) O vetor é percorrido a partir da direita até que se encontre um V[j] ≤ trab (j é decrementado no processo);
e) Os valores V[i] e V[j] são trocados; i é incrementado de 1 e j é decrementado de 1;
f) O processo é repetido até que i e j se cruzem em algum ponto do vetor;
g) Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva.

Código Fonte do Método

* QuickSort */
void quick (int n, int* v)
{
if (n <= 1)
return;
else {
int x = v[0];
int a = 1;
int b = n-1;
do {
while (a < n && v[a] <= x) a++;
while (v[b] > x) b–;
if (a < b) {          /* faz troca */
int temp = v[a];
v[a] = v[b];
v[b] = temp;
a++; b–;
}
} while (a <= b);
/* troca pivô */
v[0] = v[b];
v[b] = x;
/* ordena sub-vetores restantes */
quick(b,v);
quick(n-a,&v[a]);
}
}