Quick sort

1. A[p...r] 에서 A[r]을 기준으로 삼는다.
2. 배열 A에서, A[r]보다 작으면 A의 왼쪽, 크면 A의 오른쪽부터 채운다.
3. 세분화된 배열 A[p...q], A[q+1, r]에 대해서도 (1), (2)의 과정을 진행한다.

pseudo code of Quick sort

QUICKSORT(A, p, r)
if p < r
	q = PARTITION(A, p, r) //pivot & 정렬
    QUICKSORT(A, p, q-1) //LEFT
    QUICKSORT(A, q+1, r) //RIGHT

pseudo code of partition

PARTITION (A,p,r)
x = A[r]
i = p-1
for j = p to r - 1
	if A[j] ≤ x
    	i = i + 1
        exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1

running time of partition

$\theta(n)$ (n = r - p 일때)

running time of heap sort

1. Balanced partitioning
   • partition 후의 세분화된 두 배열의 크기가 비슷할 때 (⌊n/2⌋, ⌈n/2⌉-1)
     
   • $T(n) ≤ 2T(n/2) + Θ(n) = O(nlogn)$

2. Unbalanced partitioning
   • partition 후의 세분화된 두 배열의 크기가 심하게 비대칭인 경우하게 비대칭인 경우 (1, n-1)
   • $T(n) = T(n-1) + Θ(n)$ =$\displaystyle\sum_{k=1}^{n} Θ(k)$ = $Θ(\displaystyle\sum_{k=1}^{n} k$)
     = $Θ(n²)$
     

Worst case analysis

substitusion method로 Unbalanced partitioning의 시간 복잡도를 증명해보자.

$T(n) = max (T(q) + T(n-q-1)) + Θ(n)$ (0 ≤ q ≤ n-1)

Show that $T(n) ≤ cn²$ for some constant c.

$T(n) ≤ max (cq² + c(n-q-1)²) + Θ(n)$ (0 ≤ q ≤ n-1)

$= c • max (q² + (n-q-1)²) + Θ(n)$ (0 ≤ q ≤ n-1)

$= c • max (2q² - 2q(n-1) + (n-1)²) + Θ(n)$ (0 ≤ q ≤ n-1)

$= c • max (2(q - (n-1)/2)² + (n-1)² / 2) + Θ(n)$ (0 ≤ q ≤ n-1)

$T(n) \leq c \cdot \max_{0 \leq q \leq n-1} \left( 2(q - (n-1)/2)^2 + (n-1)^2 / 2 \right) + \Theta(n)$

$= c \cdot (n-1)^2 + \Theta(n)$

$= cn^2 - c(2n-1) + \Theta(n)$

$\le cn^2$

따라서 $-c(2n-1)+\theta(n) \le 0$ 을 만족하는 큰 c를 선택하면 $T(n) = O(n^2)$ 이다.

Average case analysis 1

worst case의 경우보다 best case의 경우에 더 가깝다. 심하게 unbalanced 한 경우에만 worst case로 분류되기 때문이다.

$\mathbb{E}[T(n)] = \frac{1}{n} \left( \sum_{q=1}^{n} \mathbb{E}[T(q-1)] + \mathbb{E}[T(n-q)] + \Theta(n) \right)$

$= \frac{2}{n} \left( \sum_{q=2}^{n-1} \mathbb{E}[T(q)] + \Theta(n)\right)$

$\mathbb{E}$: 평균, 기댓값

pivot의 위치가 1에서부터 n-1 일때까지의 모든 경우의 수의 합을 n으로 나눈 것이다.

Show that $T(n) ≤ cnlogn$ for some constant c.

1. T(k) ≤ cklogk 가 𝑘 ≤ 𝑛 − 1 (k≤n−1)에서 성립한다고 가정하자.

2. $\mathbb{E}[T(n)] = \frac{2}{n} \sum_{q=2}^{n-1} \mathbb{E}[T(q)] + \Theta(n)$

3. $\mathbb{E}[T(n)] \leq \frac{2}{n} \sum_{q=2}^{n-1} cq\log{q} + \Theta(n)$

4. $\sum_{q=2}^{n-1} q\log{q}$ 는 대략적으로 $\int_{2}^{n-1} q\log{q} dq$ 로 근사할 수 있다. (부분 적분법을 이용하여 계산한다.)

5. $\mathbb{E}[T(n)] \leq c \cdot \log{n} \cdot \frac{n(n-1)}{2n} + \Theta(n)$

6. $\mathbb{E}[T(n)] \leq cn\log{n} + \Theta(n)$

따라서 $T(n) ≤ cnlogn$ 임을 보일 수 있다.

Average case analysis 2

X를 n개의 element가 있는 배열에서 비교 횟수라고 할 때, average running time of QUICK SORT는 $T(n) = O(n + \mathbb{E}[X])$ 이다.

각 PARTITION에서 일어나는 비교 횟수를 셀 필요 없이, 전체 알고리즘 실행 동안의 비교 횟수에 대한 경계(bound) 를 도출해보자

• $z_i$: 정렬된 배열에서 i번째 작은 요소
• $Z_{ij}$ = ${z_i, z_{i+1},...,z_j}$
• $z_i$ 와 $z_j$ 는 최대 한번 (0번 또는 1번) 비교된다.
  • pivot은 한번 PARTITION에 사용되면 다시 사용되지 않는다.
  • 각 PARTITION에서 사용된 pivot은 각 요소와 비교된다.

$\mathbb{E}[X]$ = $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} Pr\{z_i \; \text{is compared to} \;z_j\}$

• $z_i$ 가 $z_j$ 와 비교되기 위해서는 둘 중 하나가 반드시 pivot이어야 한다.
• 둘 중 하나가 pivot일 확률 = $\frac{2}{j-i+1}$
• $\mathbb{E}[X]$ 는 기댓값으로, (확률 변수 값) x (확률) 이다.
• 여기서는 Bernoulli Distribution를 따른다.
  • $z_i$ 와 $z_j$ 가 서로 비교되었을 때 확률 변수: 1
  • $z_i$ 와 $z_j$ 가 서로 비교되지 않았을 때의 확률 변수: 0
• 따라서 위 식은 전체 숫자에 대해 각 쌍이 서로 비교가 되었는지를 통해 나타낸 전체 비교 연산의 기댓값이다.
  • $\mathbb{E}[X]$ = $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \{1×\frac{2}{j-i+1} + 0×\frac{j-i-1}{j-i+1}\}$
  • = $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \{\frac{2}{j-i+1}\}$

$\mathbb{E}[X]$ = $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \{\frac{2}{j-i+1}\}$ 의 계산

$k = j - i$ 라고 하자

$\mathbb{E}[X]$
= $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \{\frac{2}{j-i+1}\}$
= $\sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \{\frac{2}{k+1}\}$
< $\sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \{\frac{2}{k}\}$
($\sum_{k=1}^{n-i} \{\frac{2}{k}\}$ $\le$ $2lnn + 2$)
= $\sum_{i=1}^{n-1} O(logn)$
= $O(logn)$

Randomized quick sort

pivot을 배열의 맨 끝 값이 아닌 random하게 뽑아 진행하는 quick sort

pseudocode of randomized-quick sort

RANDOMIZED-QUICKSORT(A, p, r)
if p < r
	q = RANDOMIZED-PARTITION(A, p, r)
    RANDOMIZED-QUICKSORT(A, p, q-1)
    RANDOMIZED-QUICKSORT(A, q+1, r)
    

pseudocode of randomized-partition

RANDOMIZED-PARTITION(A, p, r)
	i = RANDOM(p, r) //p~r 범위 중 랜덤하게 선택
    exchange A[r] with A[i]
    return PARTITION(A, p, r)