[알고리즘 분석] 2장. 분할정복법(divide-and-conquer) (2)

1. 빠른 정렬(Quick Sort)

- 절대적으로 가장 빠른 정렬 알고리즘은 아님

- 분할교환정렬(partition exchange sort)의 명칭이 더 정확함

[빠른 정렬 알고리즘]
- 문제: n개의 정수를 비내림차순으로 정렬
- 입력: 정수 n > 0, 크기가 n인 배열 S[1...n]
- 출력: 비내림차순으로 정렬된 배열 S[1...n]
- 알고리즘

void quicksort (index low, index high){
    index pivotpoint;
    if (high > low){ // 데이터가 두 개 이상 존재
        partition(low, high, pivotpoint);
        quicksort(low, pivotpoint - 1);
        quicksort(pivotpoint + 1, high);
    }
}​

[분할 알고리즘]
- 문제: 빠른 정렬을 하기 위해 배열 S를 둘로 나눈다.
- 입력: 첨자 low, high, S의 부분 배열
- 출력: low에서 high까지의 S의 부분배열의 기준점(pivotpoint)
- 알고리즘

void partition (index low, index high, index& pivotpoint){
    index i, j;
    keytype pivotitem;
    pivotitem = S[low];
    j = low; //j: pivotitem 보다 작은 그룹의 제일 우측 끝 데이터의 위치
    for (i = low + 1; i <= high; i++){
        if (S[i] < pivotitem){
            j++;
            exchange S[i] and S[j];
        }
    }
    pivotpoint = j;
    exchange S[low] and S[pivotpoint]; //pivotitem 값을 pivotpoint에 넣는다. 
}

 

 

2.  quick sort 시간 복잡도 분석

1. 분할 알고리즘(partition) 분석 (모든 경우)
- 단위연산: S[i]와 pivotitem과의 비교
- 입력크기: 부분배열이 가지고 있는 항목의 수: high - low + 1
- 분석: 배열의 첫 번째 항목만 제외하고 모든 항목을 한 번씩 비교(for문에서 i = low + 1부터 시작) 
- T(n) = n - 1

2. quicksort 분석 (최악의 경우)
- 단위연산: 분할 알고리즘의 S[i]와 pivotitem의 비교
- 입력크기: 배열 S가 가진 항목의 수
- 분석: 입력이 비내림차순으로 정렬되어 있을 때가 최악의 경우이다.
- 첫번째 항목보다 작은 항목이 없으므로 0 / n-1 로 쪼개진다.
- T(n) = T(0) + T(n - 1) + n - 1, T(0) = 0
$ T(n) = T(n - 1) + n - 1 (n >0), T(0) = 0 $
$ T(n - 1) = T(n-2) + n-2 $
$ T(n - 2) = T(n-3) + n-3 $
...
$ T(2) = T(n - (n - 1)) + n-(n-1) $
$ T(2) = T(1) + 1  = 1$
$ T(1) = T(0) + 0  = 0$
$ T(0) = 0 $
$ T(n) = 0 + 0 + 1 + 2 + ... + n-1 = \frac{n(n-1)}{2} $

3. quicksort 분석 (평균의 경우)
- 단위연산: 분할 알고리즘의 S[i]와 pivotitem과의 비교
- 입력크기: 배열 S가 가지고 있는 항목의 수 
- 분석: pivotitem이 정렬 후 p번째 데이터가 될 확률($ \frac{1}{n} $), p를 기준으로 두 부분배열을 정렬하는데 걸리는 평균 시간은 A(p-1) + A(n-p), 분할하는데에 걸리는 시간은 n-1
$ A(n) = \sum_{p = 1}^{n}\frac{1}{n}[A(p-1) + A(n-p)] + n -1 $

$ = \frac{1}{n}[A(0) + A(n-1) + A(1) + A(n-2) + ... $
$ + A(n-2) + A(1) + A(n-1))+A(0)]+ n-1 $

$ = \frac{2}{n}\sum_{p=1}^{n}A(p-1) + n-1 $

$ A(n) = \frac{2}{n}\sum_{p=1}^{n}A(p-1) + n-1 $

양변에 n을 곱하면

$ nA(n) = 2\sum_{p=1}^{n}A(p-1) + n(n-1) $ ... (1)

$ (n-1)A(n-1) = 2\sum_{p=1}^{n-1}A(p-1) + (n-1)(n-2) $ ... (2)

(1) - (2)

$ nA(n) - (n-1)A(n-1) = 2A(n-1) + 2(n-1) $

$ nA(n) = (n+1)A(n-1) + 2(n-1) $

양변을 n(n+1)로 나누면

$ \frac{A(n)}{n+1} = \frac{A(n-1)}{n} + \frac{2(n-1)}{n(n+1)} $

$ a_{n} = \frac{A(n)}{n+1} $ 라고 하면,

$ a_{n} = a_{n-1} + \frac{2(n-1)}{n(n+1)} , a_{0} = 0 $

$ a_{n} = (a_{n-2} + \frac{2(n-2)}{(n-1)n}) + \frac{2(n-1)}{n(n+1)} $
...
$ a_{n} = \sum_{i=1}^{n} \frac{2(i+1)}{i(i+1)} = 2(\sum_{i = 1}^{n} \frac{1}{i+1} - \sum_{i=1}^{n} \frac{1}{i(i+1)} $

$ \sum_{i=1}^{n} \frac{1}{i(i+1)} $은 무시해도 될 만큼 작다.

$ \sum_{i = 1}^{n} \frac{1}{i+1} \approx \sum_{i=1}^{n} \frac{1}{i} = \int_{1}^{n} \frac{1}{x} dx = ln \ n $

$ a_{n} \approx 2ln\ n $

$ A(n) = (n+1)a_{n} $

$ \approx (n+1)2ln \ n $

$ = (n+1)2(ln 2)(lg\ n) $

$ \approx 1.38(n+1)lg \ n $

$ \in \Theta(nlg\ n) $


4. quicksort 분석 (Best 경우)
- 문제가 매번 반씩 나누어 질 때
$ T(n) = 2T(\frac{2}{n}) + n - 1 \in \Theta(nlg \ n ) $