تقرير
Lucky Cars and the Quicksort Algorithm
| العنوان: | Lucky Cars and the Quicksort Algorithm |
|---|---|
| المؤلفون: | Harris, Pamela E., Kretschmann, Jan, Mori, J. Carlos Martínez |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Primary 05A05, Secondary 68P10 |
| الوصف: | 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 $n$th 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\geq 2$, both counts satisfy the second order recurrence relation $ f_n=2nf_{n-1}-n(n-1)f_{n-2}+2(n-1)! $ with $f_0=f_1=0$. Comment: 8 pages, and 2 figures, to appear in The American Mathematical Monthly |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2306.13065 |
| رقم الأكسشن: | edsarx.2306.13065 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |