swMATH ID: 20694
Software Authors: Hoare, C.A.R.; Sedgewick, R
Description: On the adaptiveness of Quicksort. Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e., they have a complexity analysis that is better for inputs, which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses Ω(n log n) comparisons even for sorted inputs. However, in this paper, we demonstrate empirically that the actual running time of Quicksort is adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element swaps performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O(n(1 + log(1 + Inv/n))) element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior and gives new insights on the behavior of Quicksort. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.
Homepage: https://en.wikipedia.org/wiki/Quicksort
Related Software: Find; heapsort; Algorithm 347; Knapsack; Coq; ML; Qhull; Boost; Boost C++ Libraries; CGAL; Matlab; k-means++; UCI-ml; GitHub; QuickHeapsort; PVS; Algorithm 489; Scikit; Python; Archive Formal Proofs
Cited in: 179 Documents
all top 5

Cited by 312 Authors

7 Rösler, Uwe
5 Holmgren, Cecilia Ingrid
5 Mahmoud, Hosam M.
4 Martínez, Conrado
4 Prodinger, Helmut
4 Wild, Sebastian
3 de Boer, Frank S.
3 De Gouw, Stijn
3 Johansson, Tony
3 Kuba, Markus F.
3 Munro, J. Ian
3 Skerman, Fiona
2 Albert, Michael Henry
2 Allison, Donald C. S.
2 Broutin, Nicolas
2 Cai, Xing Shi
2 Codish, Michael
2 Cruz-Filipe, Luís
2 Deng, Xiao-Tie
2 Derigs, Ulrich
2 Devroye, Luc P. J. A.
2 Edelkamp, Stefan
2 Elmasry, Amr
2 Evans, David John
2 Fill, James Allen
2 Fouz, Mahmoud
2 Gao, Yansong
2 Grübel, Rudolf
2 Hallerstede, Stefan
2 Hoare, C. A. R. Tony
2 Hwang, Hsien-Kuei
2 Janson, Svante
2 Katajainen, Jyrki
2 Kufleitner, Manfred
2 Manthey, Bodo
2 Nebel, Markus E.
2 Noga, M. T.
2 Panholzer, Alois
2 Pisinger, David
2 Plateau, Gérard
2 Poblete, Patricio V.
2 Rot, Jurriaan
2 Sanders, Peter
2 Schneider-Kamp, Peter
2 Sulzbach, Henning
2 Wegner, Lutz Michael
2 Zeini Jahromi, Nima
2 Zhang, Jie
2 Zimmermann, Uwe T.
1 Aguech, Rafik
1 Ailon, Nir
1 Airola, Antti
1 Akaho, Shotaro
1 Ali, Montaz M.
1 Alsmeyer, Gerold
1 Alsulami, Hamed Hamdan
1 AlTurki, Musab A.
1 Amri, Anis
1 Apers, Peter M. G.
1 Apt, Krzysztof Rafal
1 Argrow, Brian M.
1 Assarsson, Ulf
1 Aumüller, Martin
1 Awile, Omar
1 Axtmann, Michael
1 Baeza-Yates, Ricardo A.
1 Bagnall, Anthony J.
1 Baranauskas, Edgaras
1 Bartoszek, Krzysztof
1 Bentley, Jon Louis
1 Bi, Guoan
1 Bingmann, Timo
1 Blum, Michael G. B.
1 Bogićević, Milica
1 Bubel, Richard
1 Büyükkeçeci, Ferit
1 Cameron, Peter Jephson
1 Cantone, Domenico
1 Ceselli, Alberto
1 Chang, Kaijung
1 Chen, Jingchao
1 Chen, Pinhan
1 Chen, Wei-Mei
1 Cheng, Ran
1 Cho, Yeol Je
1 Chopin, Nicolas
1 Chu, Jiang-Hsing
1 Cincotti, Gianluca
1 Clarkson, Kenneth L.
1 Clément, Julien
1 Cook, William R.
1 Cramer, Michael
1 Cunto, Walter
1 De Angelis, Emanuele
1 de Lima, Murilo Santos
1 Dean, Brian C.
1 Dekking, Frederik Michel
1 Dietzfelbinger, Martin
1 Ding, Wei
1 Dobosiewicz, Wlodzimierz
...and 212 more Authors
all top 5

Cited in 72 Serials

14 Information Processing Letters
14 Theoretical Computer Science
9 Algorithmica
6 Computing
5 RAIRO. Informatique Théorique et Applications
4 Formal Aspects of Computing
4 Random Structures & Algorithms
4 The Annals of Applied Probability
4 European Journal of Operational Research
4 Stochastic Processes and their Applications
3 Acta Informatica
3 Advances in Applied Probability
3 Journal of Computational Physics
3 Journal of Automated Reasoning
3 Computational Statistics and Data Analysis
3 Journal of Discrete Algorithms
2 The Annals of Statistics
2 The Computer Journal. Section A / Section B
2 Information Sciences
2 International Journal of Computer & Information Sciences
2 Statistics & Probability Letters
2 Operations Research Letters
2 Information and Computation
2 Computers & Operations Research
2 Machine Learning
2 Combinatorics, Probability and Computing
2 BIT. Nordisk Tidskrift for Informationsbehandling
2 Algorithms
1 Computers and Fluids
1 Computer Physics Communications
1 Discrete Applied Mathematics
1 The Annals of Probability
1 Applied Mathematics and Computation
1 Automatica
1 Calcolo
1 Journal of Computational and Applied Mathematics
1 Journal of Optimization Theory and Applications
1 Monatshefte für Mathematik
1 Science of Computer Programming
1 Discrete & Computational Geometry
1 International Journal of Approximate Reasoning
1 Journal of Theoretical Probability
1 Journal of Parallel and Distributed Computing
1 Signal Processing
1 Neural Computation
1 Computational Geometry
1 Journal of Global Optimization
1 Designs, Codes and Cryptography
1 Computational Statistics
1 YUJOR. Yugoslav Journal of Operations Research
1 International Journal of Computer Mathematics
1 Journal de Théorie des Nombres de Bordeaux
1 Applicationes Mathematicae
1 Journal of Difference Equations and Applications
1 European Journal of Control
1 Theory of Computing Systems
1 Mathematical Methods of Operations Research
1 Journal of Combinatorial Optimization
1 Data Mining and Knowledge Discovery
1 RAIRO. Theoretical Informatics and Applications
1 Foundations of Computational Mathematics
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 ACM Journal of Experimental Algorithmics
1 Science in China. Series F
1 ALEA. Latin American Journal of Probability and Mathematical Statistics
1 Advances in Mathematical Physics
1 International Journal of Combinatorics
1 Computer Science Review
1 Journal of Logical and Algebraic Methods in Programming
1 Other Titles in Applied Mathematics
1 Mathematics in Industry (Philadelphia)

Citations by Year