Quicksort é o algoritmo de ordenação implementado no FreeBSD (versão 14.2) e na biblioteca C do GNU (versão 2.31). Uma diferença fundamental entre eles está no algoritmo de particionamento: o GNU utiliza o particionamento do Hoare enquanto o FreeBSD usa o particionamento do Bentley-McIlroy.
Será que dá para dizer que um destes algoritmos é sempre melhor que o outro? O que descobrimos é que o melhor algoritmo depende do número de elementos repetidos no vetor. O algoritmo do Hoare é melhor em vetores sem elementos repetidos e o algoritmo do Bentley é melhor quando tem muitos elementos repetidos.
Nesse trabalho, propomos um novo algoritmo de particionamento, que chamamos de Particionamento Cearense. A proposta é de se adaptar ao número de repetições e servir como um meio termo entre os melhores algoritmos de particionamento conhecidos.
O nome do algoritmo vem dos autores deste trabalho que sou eu, Israel Mendes, Rodrigo Nogueira e Wladimir Tavares, todos cearenses, da UFC e do grupo ParGO. Acho que é bom marcar presença e colocar o nome mesmo!
Deixa de enrolar e mostra os resultados porra!!!
Experimentos geram 100 vetores de tamanho \(n\) e cada posição recebe um valor aleatório entre \(1\) e \(u\). Controlando a relação entre \(u\) e \(n\) podemos controlar o número esperado de elementos repetidos. Para o mesmo valor de \(n\), valores menores de \(u\) tem mais repetições e valores maiores tem menos.
Rodamos os experimentos em máquinas Amd e Intel dado que elas tem performance de cache bem diferentes. Os gráficos a seguir apresentam o tempo de execução medido em ciclos de CPU, então um valor menor é melhor.
Com poucas repetições
\(n = 2^8, 2^9, \dots, 2^{28}\) e \(u = n\)
AMD
INTEL
Com menos elementos repetidos, o Hoare é melhor que o Bentley. O cearense se garante e mantém a pole position, mesmo que apertado.
Com muitas repetições
\(n = 2^8, 2^9, \dots, 2^{28}\) e \(u = \sqrt{n}\)
AMD
INTEL
Com mais repetições o Bentley ultrapassa o Hoare, mas o cearense deixa eles no chinelo.
Evolução de muitas para poucas repetições
\(n = 2^{20}\) e \(u = 2^3, 2^4, \ldots, 2^{46}\)
AMD
INTEL
Aqui podemos observar o momento da ultrapassagem entre o segundo e terceiro. O cearense está cagando e andando! Ignora a briga e se adapta a qualquer situação da pista.
Mais detalhes
Para uma explicação mais detalhada, vejam a apresentação do Rodrigo, que ficou muito boa. Ele mostra o histórico do Quicksort, as ideias por trás do nosso algoritmo e algumas outras descobertas.
