Quicksort
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.
Keywords for this software
References in zbMATH (referenced in 144 articles , 3 standard articles )
Showing results 1 to 20 of 144.
Sorted by year (- Albert, Michael; Holmgren, Cecilia; Johansson, Tony; Skerman, Fiona: Embedding small digraphs and permutations in binary trees and split trees (2020)
- Bartoszek, Krzysztof: Limit distribution of the quartet balance index for Aldous’s ((\beta\ge0))-model (2020)
- Eberl, Manuel; Haslbeck, Max W.; Nipkow, Tobias: Verified analysis of random binary tree structures (2020)
- Lange, Kenneth: Algorithms from THE BOOK (2020)
- Lecué, Guillaume; Lerasle, Matthieu; Mathieu, Timlothée: Robust classification via MOM minimization (2020)
- Roesler, Uwe: Almost sure convergence to the quicksort process (2020)
- Yao, Yukun: Using nonlinear difference equations to study Quicksort algorithms (2020)
- Apt, Krzysztof R.; Olderog, Ernst-Rüdiger: Fifty years of Hoare’s logic (2019)
- Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut: Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths (2019)
- Cai, Xing Shi; Holmgren, Cecilia; Janson, Svante; Johansson, Tony; Skerman, Fiona: Inversions in split trees and conditional Galton-Watson trees (2019)
- de Gouw, Stijn; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner; Rot, Jurriaan; Steinhöfel, Dominic: Verifying OpenJDK’s sort method for generic collections (2019)
- Moore, J. Strother: Milestones from the Pure Lisp Theorem Prover to ACL2 (2019)
- Nguyen Kieu Linh; Song, Chanyoung; Ryu, Joonghyun; Phan Thanh An; Hoang, Nam-Dũng; Kim, Deok-Soo: QuickhullDisk: a faster convex hull algorithm for disks (2019)
- Wu, Yan-Xue; Min, Xue-Yang; Min, Fan; Wang, Min: Cost-sensitive active learning with a label uniform distribution model (2019)
- Aguech, Rafik; Amri, Anis; Sulzbach, Henning: On weighted depths in random binary search trees (2018)
- Gamby, Ask Neve; Katajainen, Jyrki: Convex-hull algorithms: implementation, testing, and experimentation (2018)
- Alsmeyer, Gerold; Dyszewski, Piotr: Thin tails of fixed points of the nonhomogeneous smoothing transform (2017)
- Axtmann, Michael; Witt, Sascha; Ferizovic, Daniel; Sanders, Peter: In-place parallel super scalar samplesort ((\mathrmIPS^4\mathrmo)) (2017)
- Bingmann, Timo; Eberle, Andreas; Sanders, Peter: Engineering parallel string sorting (2017)
- Codish, Michael; Cruz-Filipe, Luís; Nebel, Markus; Schneider-Kamp, Peter: Optimizing sorting algorithms by using sorting networks (2017)