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} - 4 n

comparisons on an array of size

n

ordered uniformly at random, where

H_{n} = s u m_{i = 1}^{n} f r a c 1 i

is the

n

th harmonic number. Therefore, it makes

n! l e f t [2 (n + 1) H_{n} - 4 n i g h t]

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 g e q 2

, both counts satisfy the second order recurrence relation

f_{n} = 2 n f_{n - 1} - n (n - 1) f_{n - 2} + 2 (n - 1)!

with

f_{0} = f_{1} = 0

.

Cited in

(6)

This page was built for publication: Lucky Cars and the Quicksort Algorithm