Sorting and Selecting (TODO)

QuickSort

Claim

Let $T_{l,r}$ be the (random) number of comparisons that are performed per call of $\text{QuickSort}(A,l,r)$, where $A$ is an array of pairwise different numbers. Then it holds that

$$\mathbb{E}[T_{1,n}]\le 2(n+1)\ln n+O(n).$$

Proof

For $l\ge r$ it holds that $T_{l,r}=0$. For $l<r$ it follows that

$$\begin{array}{rl}\mathbb{E}[T_{l,r}]& =\sum _{i=l}^r\mathrm{Pr}[t=i]\cdot (r-l+\mathbb{E}[T_{l,i-1}]+\mathbb{E}[T_{i+1,r}])\\ & =\frac{1}{r-l+1}\cdot \sum _{i=0}^{r-l}(r-l+\mathbb{E}[T_{l,l+i-1}]+\mathbb{E}[T_{l+i+1,r}]).\end{array}$$

Looking at this expression more closely we can find that the expected value $\mathbb{E}[T_{l,r}]$ does not actually depend on $r$ and $l$, but much rather only from the amount of elements to sort $r-l+1$. We can thus recursively define numbers $t_n$:

$$t_n=\{\begin{array}{ll}0& \text{if}n\le 1,\\ \frac{1}{n}{\sum }_{i=0}^{n-1}(n-1+t_i+t_{n-i-1})& \text{if}n\ge 2.\end{array}$$

By induction on $r-l$ we can easily see that for all $l,r$ the equality $\mathbb{E}[T_{l,r}]=t_{r-l+1}$ holds. Let’s determine an upper bound for $t_n$. For all $n\ge 3$ it holds according to above definition that

$$n\cdot t_n=\sum _{i=0}^{n-1}(n-1+t_i+t_{n-i-1}).$$

as well as

$$(n-1)\cdot t_{n-1}=\sum _{i=0}^{n-2}(n-2+t_i+t_{n-i-2}).$$

If we subtract the second from the first equation we get:

$$n{t}_n-(n-1)\cdot t_{n-1}=2(n-1)+2t_{n-1}.$$

and therefore f

$$t_n=\frac{n+1}{n}\cdot t_{n-1}+\frac{2(n-1)}{n}\le \frac{n+1}{n}\cdot t_{n-1}+2.$$

By induction over $n$ we can show that for all $n\ge 2$ that

$$t_n\le 2\sum _{i=3}^{n+1}\frac{n+1}{i}.$$

For $n=2$ it follows from the definition of $t_n$, that $t_2=1\le 2={\sum }_{i=3}^{3}1$. For $n\ge 3$ we can use the inequality $t_n\le \frac{n+1}{n}\cdot t_{n-1}+2.$ that we derived above together with the induction hypothesis.

Since ${\sum }_{i=1}^n\frac{1}{i}=H_n=\ln n+O(1)$ it holds in particular that

$$\mathbb{E}[T_{1,n}]=t_n\le 2(n+1)\ln n+O(n).$$

This proves the claim.

QuickSelect

Claim

We can find the $k$-th least element in a sequence of $n$ elements in $O(n)$ using the above $\text{QuickSelect}(A,l,r,k)$ algorithm, where $A$ is an array of pairwise different numbers.

Proof