Quickselect

Overview

Quickselect(A,l,r,k) (find the $k$-th smallest element in $\{A[l],\dots ,A[r]\}$) $p\leftarrow \text{Uniform}(\{l,l+1,\dots ,r\})$
$t\leftarrow \text{Partition}(A,l,r,p)$ //Pick the pivot $A[p]$, put it on index $t$ such that all elements on the left are smaller and all elements on the right are bigger. Return this index $t$ If $t=l+k-1$ then return $A[t]$ else if $t>l+k-1$ then return Quickselect(A,l,t-1,k) (Left block) else then return Quickselect(A,t+1,r,k-(t-l+1)) (Right block) ($k$ is the local rank)

Time Analysis

Goal: Las Vegas Algorithm with expected run time $O(n)$

We define $T=$ # of comparisons $N_j=$ # of calls of Quickselect on $m$ elements with ${\left(\frac{3}{4}\right)}^{j}n<m\le {\left(\frac{3}{4}\right)}^{j-1}n$ (we divide different sizes of problems into buckets, and our problem size is always declining)

$$T\le \sum _{j=1}^{\infty }{N}_j\underset{\begin{array}{c}\text{upper bound of}\\ \text{comparisons in}\\ \text{the partition}\end{array}}{\underbrace{{\left(\frac{3}{4}\right)}^{j-1}n}}$$ $$⟹\mathbb{E}[T]\le n\cdot \sum _{j=1}^{\infty }\mathbb{E}[N_j]{\left(\frac{3}{4}\right)}^{j-1}$$

Observation If we choose the middle half of the elements as pivot element, then the search room is reduced by factor at most $\frac{3}{4}$ (and the problem size is reduced to the next bucket) $⟹$ The search room will be reduced by factor $\le \frac{3}{4}$ with probability of $\ge \frac{1}{2}$

Claim: $\mathbb{E}[N_j]\le 2\forall j>1$ Then $\mathbb{E}[T]\le {\sum }_{j=1}^{\infty }2\cdot {\left(\frac{3}{4}\right)}^{j-1}n=8n$ (geometric serie $S=\frac{a_1}{1-p}$) Proof We also see that the pivot element is one of the middle $\frac{m_i}{2}$ elements (good pivots) with probability of $\ge \frac{1}{2}$. If we choose such good pivots, the problem size $m_i$ drops to the next bucket, and we will never call Quickselect again on this problem size. ($m_{i+1}\le \frac{3}{4}{m}_i$) Since this happens with probability $\ge \frac{1}{2}$, we must have $\mathbb{E}[N_j]\le Geom\left(\frac{1}{2}\right)=2$