Revisão das 18h13min de 15 de dezembro de 2017 editar Jessicanaiara tads (discussão \| contribs) 12 edições Quicksort utilizando dois ou mais pivôs Etiqueta: Editor Visual ← Ver a alteração anterior		Revisão das 18h19min de 15 de dezembro de 2017 editar desfazer Jessicanaiara tads (discussão \| contribs) 12 edições Quicksort utilizando dois ou mais pivôs Etiqueta: Editor Visual Ver a alteração posterior →
Linha 146: [[Imagem:Quicksort example small.png\|thumb\|Algumas etapas do algoritmo quicksort.]] Dentre inúmeras tentativas de melhorar a eficiência do quicksort clássico, em 2009 foi proposto por Yaroslavskiy (2009) o ''Dual-Pivot Quicksort''<ref name=":0">YAROSLAVSKIY, V. Dual-pivot quicksort. Research Disclosure, 2009.[http://www.kriche.com.ar/root/programming/spaceTimeComplexity/DualPivotQuicksort.pdf]</ref> , onde são utilizados 2 pivôs, particionando um array de entrada em 3 partes. Yaroslavskiy demonstra que o uso de dois pivôs é mais eficaz, especialmente quando possui uma quantidade maior de dados de entrada, comprovando a sua vantagem em relação ao algoritmo quicksort clássico. O algoritmo Dual-Pivot Quicksort, particiona um array de entrada de dados de diferentes dados primitivos (tais como, int, char, double float e long) em três partes, utilizando dois pivôs P1 e P2. Desse modo, estabelecem os seguintes ponteiros, L, K, G e left e right(índices para o primeiro e último elementos). Linha 163: # O pivô P1 é trocado com o último elemento da parte I, o pivô P2 é trocado com o primeiro elemento da parte III. # As etapas 1 e 7 são repetidas de forma recursiva para cada parte I, II e III. Também foi demonstrado por Yaroslavskiy<ref~~>YAROSLAVSKIY,~~ ~~V. Dual-pivot quicksort. Research Disclosure, 2009.[http~~name=":~~//www.kriche.com.ar/root/programming/spaceTimeComplexity/DualPivotQuicksort.pdf~~0" ~~<nowiki>[1]</nowiki>]<~~/~~ref~~> que para ordenação de dados primitivos é mais eficiente a utilização do quicksort de 3 partições, sendo o número médio de comparações do Dual-Pivot Quicksort é <math>\mathcal ({2})n\ln(n)</math>, e o número médio de trocas é <math>\mathcal ({0,8})n\ln(n)</math>, enquanto a versão clássica do algoritmo Quicksort possui <math>\mathcal ({2})n\ln(n)</math> e <math>\mathcal (1)n\ln(n)</math>, respectivamente. Uma experimento realizado pelo Budiman, Zamzami e Rachmawati (2017)<ref>BUDIMAN, M.; ZAMZAMI, E.; RACHMAWATI, D. Multi-pivot quicksort: an experiment with single, dual, triple, quad, and penta-pivot quicksort algorithms in python. In: IOP PUBLISHING.IOP Conference Series: Materials Science and Engineering. [S.l.], 2017. v. 180, n. 1, p.012051.</ref>, foi proposto, implementado e realizado experimentos com os algoritmos quicksort clássico e quicksort com dois, três, quatro e cinco pivôs. Analisando os resultados experimentais notou-se que o quicksort com um único pivô é o mais lento entre as cinco. Em segundo lugar, analisando o uso de até 5 pivôs foi comprovado que quanto mais pivôs são utilizados em um algoritmo quicksort, mais rápido seu desempenho se torna. Em terceiro lugar, o aumento de velocidade resultante da adição de mais pivôs tende a diminuir gradualmente.

Quicksort: diferenças entre revisões