3 papers
math.PR2026
Probabilistic analysis of optimal multi-pivot QuickSort
Cecilia Holmgren, Jasper Ischebeck, Daniel Krenn +2
We consider a multi-pivot QuickSort algorithm using pivot elements to partition a nonsorted list into sublists in order to proceed recursively on these subli…
math.PR2024
On fine fluctuations of the complexity of the QuickSelect algorithm
Jasper Ischebeck, Ralph Neininger
The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key com…
math.PR2024
Random -SAT: The set of atoms of the limiting empirical marginal distribution
Noela Müller, Ralph Neininger, Haodong Zhu
We show that the set of atoms of the limiting empirical marginal distribution in the random -SAT model is , for all clause-to-variable densities up to the…