Algorítmos de Ordenação - Parte V

QuickSort - Ordenação por troca de partições

Este algorítmo foi inventado por C. A. R. Hoare em 1962 e é provavelmente o mais popular algorítmo de ordenação. Ele é rápido, mas também um pouco manhoso.

A idéia básica do algorítmo é selecionarmos uma das chaves (o elemento de partição) e re-arranjamos os dados para que as chaves à esquerda do elemento de partição sejam anteriores a ela (mas não necessariamente em ordem) e as chaves à direita sejam posteriores. Repetimos o processo para as duas partições e assim por diante, até que as partições tenham um único elemento; neste ponto todos os dados estão ordenados.

Por exemplo, vamos supor que nossas chaves são [6909 6508 6407 6412 6512] e escolhemos o 6508 como elemento de partição. Um possível particionamente é [6407 6412] 6508 [6909 6512].

Uma maneira simples de particionar N chaves K₁, K₂ ... K_n é selecionar a primeira delas como elemento de partição e percorrer as chaves a partir das duas pontas, trocando de lado os elementos quando necessário. Para isto usamos dois índices, um partindo da segunda chave (i) e o outro partindo da última (j). Avançamos i até acharmos uma chave maior que K₁ (que portando deve ir para a direita) e recuamos j até acharmos uma chave menor que K₁ (que deve ir para a esquerda). Neste ponto, temos duas chaves que estão em lados errados; nós as trocamos de lugar. Quando i alcançar j, trocamos de lugar K_j com K₁, encerrando a partição.

A figura abaixo mostra uma ordenação pelo QuickSort.

O QuickSort em ação

O QuickSort tem uma natureza recursiva: após o particionamento nós usamos o mesmo algorítmo para ordenar as duas partições. Existem várias razões para não codificar o QuickSort como uma rotina recursiva:

• Chamadas a rotinas tem um overhead alto: os parâmetros precisam ser colocados na pilha do processador, um novo stack frame precisa ser criado para os parâmetros locais, etc.
• Chamadas a rotinas podem consumir uma quantidade razoável de espaço na pilha; esta quantidade não está totalmente sob o nosso controle.
• Se a pilha ficar cheia, provavelmente não conseguiremos encerrar o programa de uma forma limpa.

O que devemos fazer é codificar o QuickSort de uma forma iterativa ao invés de recursiva, gerenciando nós mesmos a pilha. A questão chave é: qual o tamanho desta pilha? Na prática, esta pilha é bem pequena, desde que coloquemos nela primeiro a partição maior e depois a menor. Desta forma, na iteração seguinte começamos com a partição menor, que por sua vez gerará um número menor de subpartições. No pior caso, a cada vez as partições serão quebradas em duas subpartições de igual tamanho, portanto o tamanho da partição é dividido continuamente por dois (mais precisamente, o tamanho diminui um pouco mais, pois o elemento de partição não entra em nenhuma das duas subpartições). Portanto, com uma pilha com k elementos podemos ordenar 2^k chaves. Ou, olhando pelo outro lado, para ordenar N chaves precisamos de uma pilha com log₂(N) elementos. Por exemplo, para ordenar um milhão de chaves basta uma pilha com 20 elementos! Cada elemento na pilha contém apenas dois inteiros (os índices do início e fim da partição a ordenar), portanto não ocupam muito espaço.

O tempo médio do QuickSort é proporciona a N log(N). Infelizmente, o pior caso é proporcional a N². Não apenas isto, escolhendo o elemento de partição da forma que descrevemos, o pior caso é quando as chaves já estão ordenadas! Neste caso, cada passo reduz o tamanho da partição de apenas uma chave (já que todas as outras serão maiores que ela). Muitas sugestões foram dadas sobre como tornar o pior caso mais improvável. Basicamente, devemos escolher melhor o nosso elemento de partição. Algumas maneiras típicas são:

• escolher aleatoreamente
• escolher a mediana dos elementos no inicio, fim e meio da partição
• escolher a mediana de uma amostra das chaves

Todos estes aperfeiçoamentos aumentam o processamento, portanto o tempo médio irá aumentar. O pior caso continua sendo proporcional a N², porém será mais difícil ele acontecer na prática.

Outro aperfeiçoamento que pode ser feito no QuickSort (e em outros) é usar um algorítimo mais simples (como a inserção direta) quando o número de elementos na partição for menor que um limite. Como já vimos, algorítimos mais simples costumam ser mais rápidos para N pequenos.

O QuickSort não é estável.

Na próxima parte vamos examinar o meu algorítmo preferido. Em seguida, nas duas partes finais, vamos finalmente ver código!