QuickSort - Ordenação por troca de partiçõesEste 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
1, K
2 ... 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
1 (que portando deve ir para a direita) e recuamos j até acharmos uma chave menor que K
1 (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
1, encerrando a partição.
A figura abaixo mostra uma ordenação pelo QuickSort.
O QuickSort em açãoO 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
2(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
2. 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
2, 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!
