Markus E. Nebel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Markus E. Nebel has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Sebastian Wild
University of Liverpool
16 shared publications - Anika Scheid
Department of Computer Science, University of Kaiserslautern, P.O. Box 3049, D-67653 Kaiserslautern, Germany
4 shared publications - Conrado Martínez
Universitat Politecnica de Catalunya
4 shared publications - Emma Yu Jin
School of Mathematical Sciences, Xiamen University, Xiamen, China
2 shared publications - Frank Weinberg
University of Kaiserslautern, Department of Computer Sciences, Gottlieb-Daimler-Strasse, D-67663 Kaiserslautern, Germany
2 shared publications Emma Yu Jin
Department of Computer Science University of Kaiserslautern 67663 Kaiserslautern Germany
1 shared publication
Latest Publications
- 13 April 2018
- Published by Springer Nature
- p. 495-521
Entwurfsmethoden für schwere Optimierungsprobleme
- 13 April 2018
- Published by Springer Nature
- p. 495-521
Entwurfsmethoden für schwere Optimierungsprobleme
- 13 April 2018
- Published by Springer Nature
- p. 399-465
Entwurfsmethoden für Algorithmen
- 13 April 2018
- Published by Springer Nature
- p. 135-231
Das Wörterbuchproblem
- 13 April 2018
- Published by Springer Nature
- p. 61-133
Elementare Datenstrukturen
- 13 April 2018
- Published by Springer Nature
- p. 233-292
Sortieren
- 13 April 2018
- Published by Springer Nature
- p. 1-59
Einleitung
- 13 April 2018
- Published by Springer Nature
- p. 341-398
String-Algorithmen
- 13 April 2018
- Published by Springer Nature
- p. 467-493
Komplexitätstheorie
- 13 April 2018
- Published by Springer Nature
- p. 293-339
Graph-Algorithmen
- Open Access
Analysis of Pivot Sampling in Dual-Pivot Quicksort
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 then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: Compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.
Open AccessAnalysis of Pivot Sampling in Dual-Pivot Quicksort
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 then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: Compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.