Quick-Sort: Uma abordagem indutiva.

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.

Idéia indutiva:

• 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.

A seguir, apresentamos a implementação completa do Quick-Sort.

• 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.