Quicksort 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; Knapsack; Coq; Algorithm 347; heapsort; ML; Matlab; k-means++; UCI-ml; GitHub; QuickHeapsort; PVS; Algorithm 489; Archive Formal Proofs; Boost C++ Libraries; Python; Scala; z3; OEIS; C4.5 Cited in: 172 Publications Standard Articles 3 Publications describing the Software, including 3 Publications in zbMATH Year On the adaptiveness of Quicksort. Zbl 1365.68190Brodal, Gerth Stølting; Fagerberg, Rolf; Moruz, Gabriel 2008 Proof of a recursive program: Quicksort. Zbl 0231.68011Foley, M.; Hoare, C. A. R. 1971 Quicksort. Zbl 0108.13601Hoare, C. A. R. 1962 all top 5 Cited by 289 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 Akaho, Shotaro 1 Ali, Montaz M. 1 Alsmeyer, Gerold 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 Berzunza Ojeda, Gabriel Hernán 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 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 1 Doerr, Benjamin 1 Doerr, Carola ...and 189 more Authors all top 5 Cited in 68 Serials 14 Information Processing Letters 13 Theoretical Computer Science 9 BIT 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 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 The Annals of Statistics 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 Journal of Global Optimization 1 Designs, Codes and Cryptography 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 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 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) all top 5 Cited in 20 Fields 126 Computer science (68-XX) 27 Probability theory and stochastic processes (60-XX) 18 Operations research, mathematical programming (90-XX) 16 Combinatorics (05-XX) 15 Statistics (62-XX) 13 Numerical analysis (65-XX) 4 Fluid mechanics (76-XX) 4 Biology and other natural sciences (92-XX) 3 Mathematical logic and foundations (03-XX) 3 Number theory (11-XX) 3 Convex and discrete geometry (52-XX) 2 General topology (54-XX) 2 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Systems theory; control (93-XX) 1 General and overarching topics; collections (00-XX) 1 Difference and functional equations (39-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Operator theory (47-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year