Lucky Cars and the Quicksort Algorithm

Abstract

Quicksort is a classical divide-and-conquer sorting algorithm. It is a comparison sort that makes an average of $2(n+1)H_n-4n$ comparisons on an array of size n ordered uniformly at random, where $H_n:={\sum }_{i=1}^n\frac{1}{i}$ is the nth harmonic number. Therefore it makes $n!\left[2(n+1)H_n-4n\right]$ comparisons to sort all possible orderings of the array. In this article, we prove that this count also enumerates the parking preference lists of n cars parking on a one-way street with n parking spots resulting in exactly $n-1$ lucky cars (i.e., cars that park in their preferred spot). For $n\ge 2$, both counts satisfy the second order recurrence relation $f_n=2n{f}_{n-1}-n(n-1)f_{n-2}+2(n-1)!$ with $f_0=f_1=0$.

MSC:

• 05A19
• 68R05

ACKNOWLEDGMENT

We thank the Editorial Board and the anonymous referees for their careful review and suggestions. P. E. Harris was supported through a Karen Uhlenbeck EDGE Fellowship. J. C. Martínez Mori was partially supported by NSF Grant No. 2144127, awarded to S. Samaranayake. J. C. Martínez Mori is supported by Schmidt Science Fellows, in partnership with the Rhodes Trust.

DISCLOSURE STATEMENT

No potential conflict of interest was reported by the authors.

Notes

1 In practice, Quicksort is implemented in conjunction with non-recursive sorting algorithms that work well on small arrays. This and other practical optimizations of the algorithm are described by Sedgewick in [8].

2 Given $f,g:\mathbb{N}\to \mathbb{N}$, we say $f=O(g)$ if there exist $k\in \mathbb{N}$ and $C\in {\mathbb{R}}_{>0}$ such that $f(n)\le C\cdot g(n)$ for all $n\ge k$.

Additional information

Funding

J. C. Martínez Mori was partially supported by NSF Grant No. 2144127, awarded to S. Samaranayake. J. C. Martínez Mori is supported by Schmidt Science Fellows, in partnership with the Rhodes Trust.

Notes on contributors

Pamela E. Harris

PAMELA E. HARRIS received her Ph.D. degree in mathematics from the University of Wisconsin, Milwaukee, held a postdoctoral position at the United Stated Military Academy, and is now an Associate Professor of Mathematics at the University of Wisconsin, Milwaukee. Her research interests are in algebra and combinatorics, particularly as these subjects relate to the representation theory of Lie algebras. Her service commitments aim to increase the visibility of Latinx and Hispanic mathematicians via platforms such as lathisms.org.

Department of Mathematical Sciences, University of Wisconsin, Milwaukee

[email protected]

Jan Kretschmann

JAN KRETSCHMANN received his Ph.D. from the University of Wisconsin, Milwaukee. His research interests are in algebraic combinatorics and enumerative combinatorics.

Department of Mathematical Sciences, University of Wisconsin, Milwaukee

[email protected]

J. Carlos Martínez Mori

J. CARLOS MARTÍNEZ MORI is a Schmidt Science Fellow and a President’s Postdoctoral Fellow at the Georgia Institute of Technology. He completed his Ph.D. degree at the Center for Applied Mathematics at Cornell University. His research interests are in discrete optimization, combinatorics, and algorithmic fairness. Consistent with Hispanic naming conventions, he embraces his two surnames in formal settings (e.g., academic authorship).

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332

[email protected]