Zhancun Mu

I am a student at PKU and here is my blog.

1 minute read

Video Link

Steps

steps:

  1. Divide: partition array in to 2 subarrays around pivot $x$ s.t. elems in lower array $\leqslant x \leqslant$ elems in upper array
  2. Conquer: recursively sort 2 subarrays
  3. Combine: trival

Key: linear time ($\Theta(n)$) partitioning subroutine.

def partition(A, p, q) # A[p,...,q]
  x = A[p] # pivot
  i = p
  for j in range(p+1,q+1):
    if A[j] <= x:
      i = i + 1
    swap(A[i], A[j])
    swap(A[p],A[i])
  return i

def quicksort(A, p, q):
  if p < q:
    r = partition(A, p, q)
    quicksort(A, p, r - 1)
    quicksort(A, r + 1, q)

Analysis

assume all elems distinct

worst time:

  • input sorted or reverse sorted. one side of partitions has no elems \(T(n) = T(0) + T(n-1) + \Theta(n) = \Theta(n^2)\)

best case:

  • partition splits the array $\frac{n}{2}: \frac{n}{2}$ \(T(n)=2T\left( \frac{n}{2} \right)+\Theta(n)=\Theta(n\log n)\)

Randomized quicksort

  • running time independent of input ordering
  • no assumptions about input distribution
  • no specific input elicits the worst behavior(only by RNG)

pivot on rand elem

$T(n) =$ r,v for running time assuming the random numbers are independent

for $k=0,1,\dots,n-1$ let

\[X_{k} = \begin{cases} 1, & \text{if partition generates} \ k:n-k-1 \ \text{split} \newline 0, & \text{otherwise} \end{cases}\]

Indicator random variable

\[E[X_{k}] = \frac{1}{n}\] \[T(n)=\begin{cases} T(0)+T(n-1)+\Theta(n) ,&\text{if}\ 0:n-1 \ \text{split} \newline &\vdots \newline T(n-1)+T(0)+\Theta(n) ,&\text{if}\ n-1:0 \ \text{split} \end{cases}\] \[T(n)=\sum_{k=0}^{n-1}X_{k}(T(k)+T(n-1-k)+\Theta(n))\] \[\begin{align} E(T(n)) &= E\left[ \sum_{k=0}^{n-1}X_{k}(T(k)+T(n-1-k)+\Theta(n)) \right] \newline &= \sum_{k=0}^{n-1}E[X_{k}(T(k)+T(n-1-k)+\Theta(n))] \newline &= \sum_{k=0}^{n-1}E[X_{k}]\cdot E[T(k)+T(n-1-k)+\Theta(n)] \newline &= \frac{1}{n}\sum_{k=0}^{n-1}E[T(k)]+\frac{1}{n}\sum_{k=0}^{n-1}E[T(n-1-k)]+\Theta(n) \newline &= \frac{2}{n}\sum_{k=0}^{n-1}E[T(k)]+\Theta(n) \newline &= \frac{2}{n}\sum_{k=2}^{n-1}E[T(k)]+\Theta(n) \end{align}\]

Prove $E[T(n)]\leqslant an\lg n$ for some $a>0$: Base case: choose $a$ big enough s.t. $an\lg n\geqslant E[T(n)]$ for small $n$ Use fact: $\sum_{k=2}^{n-1}k\lg k \leqslant \frac{1}{2} n^2 \lg n -\frac{1}{8}n^2$ Substitution:

\[\begin{align} E[T(n)] & \leqslant \frac{2}{n} \sum_{k=2}^{n-1}ak\lg k+\Theta(n) \newline & \leqslant an\lg n - \frac{a}{4}n+\Theta(n) \newline & \leqslant an\lg n \quad \text{if} \ a\geqslant 4 \end{align}\]

Comments

You May Also Enjoy