ISSN 2317-3297
Quicksort e Quicksort Aleatorizado: Um estudo comparativo
Fábio Henrique de Farias,
Fabiano Barbosa Mendes da Silva,
José Belmiro Neto
Universidade Federal Rural de Pernambuco - UFRPE
Unidade Acadêmica de Garanhuns
55296-901, Garanhuns, PE
E-mail: [email protected].
Palavras-chave: Algoritmo, Ordenaçãoo, Particionamento, Vetor aleatório, Complexidade.
Resumo: Neste estudo, evidenciamos um método para a ordenação de elementos que visa um
menor custo computacional: o quicksort aleatorizado. Este método utiliza amostragem aleatória
durante a realização de uma sub-rotina (particionamento), obtendo um bom tempo de execução
no caso médio (em geral, bem melhor que o quicksort, com o qual o comparamos) e nenhuma
entrada especı́fica induz o seu comportamento ao pior caso. Apresentamos ainda resultados obtidos de testes preliminares com os dois métodos, tabulando segundo alguns critérios selecionados,
tais como o tempo de execução e a quantidade de trocas.
1
Introdução
O algoritmo quicksort (QS) é um algoritmo de ordenação cujo tempo de execução no pior caso é
da ordem de Θ(n2 ) sobre um arranjo de entrada de n números. Apesar desse tempo de execução
ser lento no pior caso, este algoritmo é frequentemente usado como uma boa opção prática
para ordenação, devido a sua grande eficiência na média, cujo tempo de execução esperado é
Θ(nlogn) e os fatores ocultos nesta notação são muito pequenos. Apresenta ainda a vantagem
de ordenação local e funciona bem até em ambientes de memória virtual. O quicksort baseia-se
no paradigma da divisão e conquista. Esse processo de dividir e conquistar, segundo Cormen
[1], é realizado em três passos: dividir, conquistar e combinar.
2
O Quicksort
O algoritmo quicksort recebe um vetor A[p...r] e o rearranja em ordem crescente. Seu desempenho depende do fato do particionamento ser balanceado ou não balanceado e isso depende de
quais elementos são usados para particionar. Se o particionamento é balanceado, o algoritmo
é executado assintoticamente tão rápido quanto a ordenação por intercalação. Porém, se ele é
não balanceado, o algoritmo pode ser executado assintoticamente tão lento quanto a ordenação
por inserção.
O Subproblema da Separação: A parte principal do algoritmo quicksort objetiva a resolução do seguinte problema: rearranjar A[p...r] de modo que todos os elementos pequenos
fiquem na parte esquerda do vetor e todos os elementos grandes fiquem na parte direita. Este
é o subproblema da separação (particionamento), cujo ponto de partida para determinar sua
88
ISSN 2317-3297
solução é a escolha de um ”pivô”, digamos x. Os elementos do vetor que forem maiores que x
serão considerados grandes e os demais serão considerados pequenos. É preciso escolher x de tal
modo que cada uma das duas partes do vetor rearranjado seja estritamente menor que o vetor
todo [2].
Desempenho: Realizamos os estudos de desempenho para o pior caso, para o melhor caso
e para o caso médio. Para o primeiro deles, após alguns cálculos, concluı́mos que seu tempo de
execução não é melhor do que o da ordenação por inserção, que é executada no tempo O(n).
Na divisão mais uniforme possı́vel, o algoritmo produz dois subproblemas, cada um de tamanho
não maior que n = 2, pois um tem tamanho ⌊n/2⌋ e o outro tem tamanho ⌈n/2⌉ − 1. Nesse caso,
o Quicksort (QS) é executado com muito mais rapidez. A recorrência pelo tempo de execução
é então T (n) ≤ 2T (n/2) + Θ(n), que, segundo o Teorema Mestre ([1], p.59), tem a solução
T (n) = O(nlgn). O tempo de execução do caso médio de QS é muito mais próximo do melhor
caso que do pior caso. Isso decorre do fato de que o equilı́brio do particionamento se reflete
na recorrência que descreve o tempo de execução. Desse modo, com uma divisão realizada em
qualquer proporção constante, o quicksort tem custo total de O(nlgn).
3
O Quicksort Aleatorizado
O quicksort aleatorizado (QSA) é obtido a partir do QS, utilizando-se uma técnica denominada amostragem aleatória, que consiste em, ao invés de sempre usar A[r] como pivô, utiliza
um elemento escolhido ao acaso a partir do subarranjo A[p...r]. Essa modificação assegura que
o elemento pivô x = A[r] tem a mesma probabilidade de ser qualquer um dos r − p + 1 elementos do subarranjo. Como o elemento pivô é escolhido ao acaso, espera-se que a divisão do
arranjo de entrada seja razoavelmente bem equilibrada na média. Os algoritmos utilizados são
RANDOMIZED-PARTITION e RANDOMIZED-QUICKSORT (ver [1]).
Desempenho do Algoritmo de Separação Aleatorizado: Segundo Cormen ([1], pp.125126), o tempo de execução do caso médio de RANDOMIZED-QUICKSORT é O(nlgn), pois, se
em cada nı́vel de recursão a divisão induzida por RANDOMIZED-PARTITION colocar qualquer
fração constante dos elementos em um lado da partição, então a árvore de recursão terá a
profundidade Θ e o trabalho O(n) será executado em cada nı́vel. Ainda que sejam adicionados
novos nı́veis com a divisão mais desequilibrada possı́vel entre esses nı́veis, o tempo total de
execução continuará a ser O(nlgn). Para realizar uma análise precisa sobre o tempo de execução
de RANDOMIZED-QUICKSORT, deve-se compreender o procedimento de particionamento e
como consequência derivar um limite O(nlgn) sobre o tempo esperado. Esse limite superior,
combinado com o limite do melhor caso Θ(nlgn) resulta em um tempo de execução esperado [4]
de Θ(nlgn).
Analisamos o pseudocódigo e em seguida o implementamos, a partir de alguns exemplos, em
linguagem JAVA. A execução dos testes durou cerca de 4 horas, produzindo dados, que foram
analisados e dispostos de forma simplificada. Para tal, usamos os métodos estáticos não instanciados a objetos quaisquer, para eliminar operações. A ferramenta utilizada foi Eclipse JAVA
EE IDE for Web Developers. Version: Helios Service Release 2, disponı́vel em 12 computadores
pessoais com a seguinte configuração: Processador Intel Core 2 Quad Q8200 de 2.33GHz com
memória de 2 GB com sistema operacional Windows Vista Business 32-bits. Foram criados três
vetores, um para armazenar o vetor gerado aleatoriamente, outro para armazenar uma cópia
do vetor aleatório, que foi utilizado para efetuar a ordenação através do QS e por último um
vetor, que também foi uma cópia daquele, para efetuar a ordenação pelo QSA. O segundo vetor
foi ordenado uma vez, e o terceiro foi ordenado n vezes, isto é, após cada ordenação foi feita
uma cópia do vetor original no terceiro, para que ele fosse ordenado novamente. Por fim, foram criados três grupos de trabalho. O primeiro (G1) foi composto por 24 vetores de tamanho
100.000, em que cada um deles foi ordenado no QS uma vez e ordenado no QSA 10.000 vezes. O
89
ISSN 2317-3297
segundo (G2), de forma análoga à primeira, tinha 1040 vetores de tamanho 10.000, ordenados
no QSA 2.000 vezes. Por último, no grupo G3, de modo análogo, foram criados 8.000 vetores
de tamanho 1.000 e ordenados em QSA 500 vezes.
Resultados e Discussão: Em G1, houve 240.000 ordenações no QSA, no qual verificamos
que, em geral, 3,82 % das ordenações tiveram um resultado melhor que na ordenação pelo QS.
Nesse grupo, todos os 24 vetores utilizados obtiveram um ou mais resultados positivos a favor
da ordenação aleatória. Observamos que no QSA ouve uma diminuição de até 3.927 trocas,
mas que também ocorreu um acréscimo de até 8.316 trocas, em determinados casos. Para o
G2, os 1.040 vetores foram ordenados 2.080.000 vezes no QSA. Genericamente, 8,43 % destas
ordenações deixaram o QSA em vantagem. As maiores discrepâncias foram 1.466 trocas a favor
do QSA e em seguida o contrário: 1.526 a favor do QS (o QSA teve mais passos). Observamos
ainda que 192 vetores não conseguiram ser ordenados mais eficientemente no QSA. No grupo G3,
foram criados 8.000 vetores e ordenados 4.000.000 de vezes. Em 20,09 % das ordenações o QSA
foi novamente mais eficiente, pois conseguiu até 207 passos a menos que o QS. Os resultados
obtidos através desses testes preliminares, reforçam a ideia de que a utilização do randomizedquicksort é uma alternativa bastante interessante, pois representa uma evolução, a menos de
pequenas modificações do quicksort, posto que, em média, estabelece um tempo de execução
muito menor do que o algoritmo original. Desse modo, além do aprofundamento dos estudos
de complexidade desse algoritmo, este trabalho desperta o interesse em estabelecer comparações
entre outras técnicas que utilizem uma componente aleatória para a resolução de problemas de
ordenação, o que deve possibilitar a criação de algoritmos mais eficientes para solucionar essa
categoria de problemas.
Tabela 1: Resumo do estudo comparativo entre QS e QSA
Grupos
G1
G2
G2
Tamanho do vetor
100.000
10.000
1.000
Quantidade de vetores
24
1.040
8.000
Tentativas QSA por vetor
10.000
2.000
500
Total de tentativas
240.000 2.080.000 4.000.000
Eficiência global QSA
3.82 %
8.43 %
20.09 %
Ineficiência QSA (Vetores)
0
192
129
Vantagem QSA (Passos)
3.927
1.466
207
Desvantagem QSA (Passos)
8.316
1.526
212
Referências
[1] T. H.Cormen, et al, Algoritmos: ”Teoria e Prática”. Tradução da 2a edição do ”Introduction
to Algorithms”, Rio de Janeiro: Elsevier, 2008.
[2] P. Feofiloff, ”Análise do Algoritmo Quicksort”. Notas de aula. Disponı́vel em:
http://www.ime.usp.br/pf/analisedealgoritmos. Acesso em 01 de Nov. 2011.
[3] V. Ramachandran, ”Randomized Quicksort. Lecture 6”. University of Texas at Austin.
Disponı́vel em: http://docs.google.com/ userweb.cs.utexas.edu/lr/s07.357/notes/lec6.pdf+
quicksort +randomized+running+time. Acesso em: 01 nov. 2011.
[4] D.Gildea, ”Design and Analysis of Efficient Algorithms. Lecture 7”. University of Rochester.
Disponı́vel em: http://www.cs. rochester.edu/gildea/csc282. Acesso em 01 nov. 2011.
90