Abstrato

Engenharia de um algoritmo de particionamento Quicksort

D.Abhyankar e M.Ingle

Um dos algoritmos de classificação mais sofisticados na literatura de classificação é o Quicksort. Embora o Quicksort tenha vários aspetos marcantes, o design da função de partição é o aspeto central do algoritmo Quicksort. O particionamento é uma área meticulosamente pesquisada na qual encontramos a Partição Hoare e a Partição Lomuto como dois algoritmos de partição proeminentes na literatura. Apesar de muitos esforços terem sido direcionados para a investigação sobre o particionamento, parece que o particionamento é ainda inadequadamente compreendido e passível de uma combinação certa de otimizações. Os algoritmos de particionamento superiores podem ser concebidos utilizando uma combinação perfeita de medidas de melhoria de desempenho e um toque de elegância. Este artigo postula dois novos algoritmos de partição que são melhores que os existentes. O algoritmo3 proposto aplica algumas otimizações eficazes e, por causa disso, a contagem de instruções é reduzida. A contagem reduzida de instruções ajuda a função a obter um desempenho espetacular. O algoritmo apresentado4 é um algoritmo elegante, compacto e intensamente competitivo do ponto de vista do desempenho.