[알고리즘] Quick sort(퀵소트) 이론 정리

특징:

Worst case에 대해서는 $O(n^2)$ 시간이지만,

Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다.

 

전략:

Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법

 

*단계:

1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 

2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔)

3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다.

 

* 분할 정복 알고리즘 수도 코드:

solve(I)
	n=size(I)
    if(n<= smallsize)
    	solution = directlysolve(I); // conquer
    else
    	divide I into I_1, ... , I_k // divide
        for each i in {1, ... , k}
        	s_i = solve(I_i);
        solution = combine(S_1, ... , S_k); //combine
    return solution;

최소 단위에 대한 해결 방법을 정의 하고,

최소 단위가 아니라면 최소단위가 될때까지 분할하여 해결한 후,

그 값들을 조합하여 값을 반환한다.

 

알고리즘:

분할 정복 기반으로 랜덤하게 값(pivot)을 뽑아내어, 그 pivot을 기준으로 작은 그룹(L), 같은 그룹(E), 큰 그룹(G)으로 나누어 재귀적으로 처리한다.

divide: 값 추출 및 비교하여 각 그룹으로 분리

conquer: 각 그룹을 같은 방식으로 분리하여 정렬

combine: L,E,G를 다시 결합한다.

 

아래는 각 그룹으로 나누는 수도코드 이다.

Algorithm partition(S,p)
	Input sequence S, position p of pivot
    Output subsequences L,E,G of the elements of S
    
    L,E,G <- empty sequences
    x <- S.remove(p) // O(1) time
    
    while !S.isEmpty() // O(n) time
    	y <- S.remove(S.first()) // O(1) time
        if y < x
        	L.insertLast(y) // O(1)
        else if y = x
        	E.insertLast(y) // O(1)
        else
        	G.insertLast(y) // O(1)
    return L,E,G

pivot을 제외하고 남은 것들을 하나씩 비교하면서 그룹을 분리한다.

위 코드를 보면 분할 하는 작업이 O(n)이 걸림을 알 수 있다.

분석:

*Worst-case Running Time

최악의 경우는 매 시행의 pivot이 가장 작거나 크거나 할 경우를 말한다.

그 이유는 한 그룹으로 계속 몰려야 최대한으로 중복되게 비교연산을 수행하기 때문이다.

따라서 input size = n 에 대하여 한번 수행시 L or G는 n-1개, 남은 그룹은 0개이고 비교연산은 n-1번 수행한다.

 

재귀적으로 계속 내려가면 총 비교 연산은 다음과 같다.

$n + (n-1) + ... + 2 + 1 = \sum\limits_{i=1}^{n} i = \cfrac{n(n+1)}{2} \in O(n^2)$

따라서 퀵소트의 최악의 수행시간은 $O(n^2)$ 이다.

 

*Average-case Running Time (informal analysis)

pivot의 위치를 $L:G = 1:3$인 지점으로 잡았다고 가정하자.

그렇게 될때, 이진 트리 형태로 나타낸다면, level 당 O(n) 시간으로 비교연산을 실행하고,

G그룹 쪽으로 재귀적으로 계속 내려가면, 최대 depth가 나온다.(G가 L보다 크기가 크기 때문)

이때 depth를 k라고 하면, k번까지 내려가면 그룹의 크기는 최소 단위인 1 이 될 것이다.

이를 식으로 나타내면 다음과 같다.

 

$n\times(\cfrac{3}{4})^k = 1$

$n=(\cfrac{4}{3})^k $

 

식을 k에 대해 정리하면

$\therefore k=\log_{\frac{4}{3}} n  = \cfrac{\log_{2} n }{\log_{2} \frac{4}{3} }$

$ \le c\log_{2} n \in \theta(\lg n)$ (식을 만족하는 c 존재)

 

height가 O(logn) 이고, level 당 O(n) 시간이 걸리므로 둘이 곱하면 연산 평균시간을 구할 수 있다.

 

$\therefore O(n\lg n) \text{ time}$

 

다른 비율도 같은 방법으로 증명이 가능하다.

위 식을 s,t로 일반화 하여 분석 해보자.

$L:G = s:t (s < t, s\ne0)$

t가 더 크다는 가정을 하면, 최대 depth는 G 그룹을 재귀적으로 분할 하였을 때이므로,

height를 k라고 하면, k번 까지 내려가면 그룹의 크기가 최소 단위인 1 이 될 것이다.

똑같이 식으로 나타내면 다음과 같다.

 

$n\times(\cfrac{t}{s+t})^k = 1$

 

$n=(\cfrac{s+t}{t})^k $

 

식을 k에 대해 정리하면

$\therefore k=\log_{\frac{s+t}{t}} n  = \cfrac{\log_{2} n }{\log_{2} \frac{s+t}{t} }$

$\log_{2} \frac{s+t}{t} = \log_{2} (1+\frac{s}{t}) \ge 0$ 이므로

$k \le c\log_{2} n \in \theta(\lg n)$ (식을 만족하는 c 존재)

 

동일하게 height가 O(logn) 이고, level 당 O(n) 시간이 걸리므로 둘이 곱하면 동일한 평균시간을 구할 수 있다.

$\therefore O(n\lg n) \text{ time}$