Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Analysis of pivot sampling in dual-pivot Quicksort: A holistic analysis of Yaroslavskiy's partitioning scheme

Autor
Nebel, M.; Wild, S.; Martinez, C.
Tipus d'activitat
Article en revista
Revista
Algorithmica
Data de publicació
2016-08
Volum
75
Número
4
Pàgina inicial
632
Pàgina final
683
DOI
https://doi.org/10.1007/s00453-015-0041-7 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/89895 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs00453-015-0041-7 Obrir en finestra nova
Resum
The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-015-0041-7 The new dual-pivot Quicksort by Vladimir Yaroslavskiy-used in Oracle's Java runtime library since version 7-features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort...
Citació
Nebel, M., Wild, S., Martínez, C. Analysis of pivot sampling in dual-pivot Quicksort: A holistic analysis of Yaroslavskiy's partitioning scheme. "Algorithmica", Agost 2016, vol. 75, núm. 4, p. 632-683.
Paraules clau
Quicksort, Dual-pivot, Yaroslavskiy's Partitioning Method, Median Of Three, Average-case Analysis, I/o Operations, External-memory Model
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius