Neste post, vamos fazer uma análise indutiva do método de ordenação que na prática é o mais rápido. O quick-sort demostra a eficiência do paradigma "dividir e conquistar".
O primeiro passo do quick-sort é escolher aleatoriamente um elemento x que será chamado de pivô. Em seguida, o vetor será particionado de forma que os elementos a esquerda do pivô sejam menores que ele, e os elementos a direita sejam maiores ou iguais a ele. A Figura 1 apresenta uma partição cujo pivô é 4.
 |
| Figura 1. Vetor particionado |
Descrição indutiva da "partição": Para construir o nosso algoritmo vamos utilizar a abordagem indutiva, detalhando o caso base, a hipótese de indução e o caso geral..
Idéia indutiva:
- Caso Base: o vetor possui apenas 1 elemento, então ele já está particionado!
- Hipótese de Indução: vamos supor que o problema da partição já está resolvido para n - 1 elementos e que sabemos onde termina a lista de elementos menores que o pivô.
- Caso Geral: é quase trivial, pois basta verificar se o último elemento do vetor é menor ou maior que o pivô. Caso o último elemento seja menor que o pivô, então basta colocá-lo no final da lista de elementos menores que o pivô.
Implementação da partição: Seguindo o esquema indutivo apresentado, podemos implementar um método de forma simples. Nessa implementação, o pivô escolhido é o primeiro elemento do vetor.
- Implementação em C++:
int partition(int X[], int left, int right) {
int pivot = X[left];
int i = left;
for (int j = left; j <= right; j++)
if (X[j] < pivot)
swap(X, j, ++i);
swap(X, left, i);
return i;
}
Após a execução do método "partition", apenas o pivô estará na posição correta. Precisamos ordenar os elementos que estão à esquerda e à direita do pivô. No entanto, podemos assumir que a hipótese de indução fará esse trabalho, como podemos ver na Figura 2. |
| Figura 2. |
- Caso Base: um vetor com 1 elemento já está ordenado.
- Hipótese de Indução: após a execução do método "partition", vamos assumir que a hipótese de indução sabe como ordenar todos os elemento que estão à esquerda e à direita do pivô.
- Caso Geral: simplesmente já temos o vetor ordenado!
Na Figura 3, apresentamos o resultado final, um vetor ordenado!
 |
| Figura 3. Vetor ordenado. |
- Implementação em Haskell: por se tratar de uma linguagem funcional, Haskell permite que o programador implemente uma solução enxuta, sem se preocupar com detalhes.
quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort [x] = [x]
quickSort (x:xs) = quickSort menores ++ [x] ++ quickSort maiores
where
menores = [p | p <- xs, p <= x]
maiores = [p | p <- xs, p > x]
- Implementação em C++
void quickSort(int A[], int left, int right){
if(left < right){
int middle = partition(A, left, right);
quickSort(A, left, middle - 1);
quickSort(A, middle + 1, right);
}
}
- Implementação em Python
def quickSort(lista): if lista == []: return [] else: pivot = lista[0] menores = [x for x in lista[1::] if x < pivot] maiores = [x for x in lista[1::] if x >= pivot] return quickSort(menores) + [pivot] + quickSort(maiores)
Complexidade do Quick-Sort: A complexidade do algoritmo depende da escolha do pivô, caso o pivô escolhido divida o vetor em duas partes com tamanhos iguais ou similares, a sua complexidade será O(n log n).
Caso os elementos do vetor já estejam ordenados, a complexidade do Quick-Sort no pior caso será descrita pela recorrência $T(n) = T(n - 1) + O(n) = O(n^2)$. Na prática, como o pior caso raramente acontece, a literatura reconhece que o Quick-Sort é o melhor algoritmo de ordenação, e por isso ele é utilizado em uma grande variedade de aplicações.
