Desenvolvido em 1962
por Tony Hoare, o quicksort é um dos métodos de ordenamento mais
rápidos e eficientes quando comparado com outros algoritmos de
complexidade O(n*log(n)). No pior dos casos a complexidade sobe para O(n2 ) mas isso é bastante raro e actualmente o quicksort destaca-se como um dos melhores algoritmos de ordenamento.
O ALGORITMO
1. Escolher
um elemento do array de entrada para ser o pivot. A maneira mais
simples seria utilizar o elemento que está no meio do array. Apesar de
não estar errada, é uma opção que por vezes está na origem do aumento da
complexidade do algoritmo (já deu para perceber que pivot e
complexidade estão relacionados aqui, right?). Uma melhor opção seria a
mediana entre o valor central e os valores extremos do array, como
exemplificamos mais abaixo.
2. Reordenar
o array de modo a que a parte esquerda seja apenas composta por
elementos menores que o pivot e a parte direita por elementos maiores
que o pivot. No fim deste processo de partição temos um array reordenado
onde o pivot se encontra rodeado em ambos os lados por uma sub-lista
não ordenada.
3. De forma
recursiva ir dividindo sucessivamente cada uma das sub-listas e aplicar
as operações acima descritas (encontrar o pivot e fazer a partição) a
cada nova sub-lista que vai surgindo. No final teremos uma sequência
ordenada por ordem crescente.
A operação de partição é crucial no quicksort, assim sendo, é importante aplicar um algoritmo rápido e eficiente. Aqui abordamos o chamado Algoritmo de Partição de Hoare com algumas optimizações acrescentadas. Para além de eficiente, é um algoritmo relativamente fácil de compreender e de implementar. A acompanhar os passos do algoritmo vai um exemplo baseado no array de entrada da figura anterior.
1. A função de partição recebe três argumentos: o array de entrada e os indíces que delimitam a sub-lista desse array a que será aplicada a partição. O indíce inferior será denominado por left e o superior por right. A sub-lista será identificada como A. O primeiro passo será encontrar o pivot para essa sub-lista e, posteriormente, trocá-lo com o elemento que está na última posição ( A[right] ). Deverão ser declaradas duas variáveis auxiliares: uma variável i para percorrer A da esquerda para direita e uma variável j para percorrer a sub-lista no sentido contrário.
2. Enquanto A[i] < pivot, o i é incrementado, parando quando essa condição se deixa de verificar. Por outro lado, o j é decrementado enquanto A[j] > pivot. Quando ambas as condições se deixarem de verificar, e se i e j ainda não se tiverem cruzado, trocamos os dois elementos. Caso i>= j, a sub-lista já está reordenada, por isso voltamos a colocar o pivot no sítio certo e retornamos o indíce i em que parámos.
3. Temos então duas sub-listas que, apesar de já terem sofrido partição, não estão ainda ordenadas por ordem crescente, que é o objectivo do quicksort. Tal objectivo será alcançado através das inúmeras divisões que vamos fazendo ao array inicial, como já foi explicado em cima, aplicando este método de partição a cada nova sub-lista. A divisão é sempre feita no índice onde ficou o pivot - por isso é que retornamos a variável i no fim de toda a partição feita. Por cada divisão que fazemos são duas novas partições que temos de fazer: uma para a sub-lista que vai de A[0] a A[i-1] e outra para a sub-lista que vai de A[i+1] a A[len(A)].
PSEUDO-CÓDIGO
0 comentários:
Enviar um comentário