7. Quicksort

퀵 정렬은 최악 수행 시간이 \Theta(n^{2})이지만 평균 수행 시간이 \Theta(n \lg n)이며 수행 시간 비례 상수가 작으므로 실제로는 많이 쓰인다. 또한 제자리 정렬 알고리즘이기도 하다.

7.1. Description of quicksort

퀵 정렬은 병합 정렬과 비슷하게 분할 정복 방식을 사용한다.

분할: 부분배열 A[p, \cdots, r]A[p, \cdots, q - 1]A[q + 1, \cdots, r]로 나눠서 전자는 A[q] 이하로, 후자는 이상이 되게 한다. 기준 인덱스 q는 분할 과정에 속한다.

정복: 두 부분배열 A[p, \cdots, q - 1]A[q + 1, \cdots, r]을 퀵 정렬의 재귀 호출로 정렬한다.

결합: 두 부분배열이 정렬되어 있고 A[q]가 기준점이므로 추가 작업은 불필요하다.

이를 쓰면 다음과 같다. 최초에는 QUICKSORT(A, 1, A.length)가 호출된다.

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

핵심은 PARTITION 부분이다. 이는 x = A[r]을 기준점으로 삼아 배열을 4개의 부분으로 나눈다.

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

루프가 돌 때마다, 배열은 다음의 4부분으로 나뉘며 이것이 루프 불변 조건이다.

  • p \leq k \leq iA[k] \leq x이다.
  • i + 1 \leq k \leq j - 1이면 A[k] > x이다.
  • k = r이면 A[k] = x이다.
  • j \leq k \leq r - 1은 x와 특별한 관계는 없다.

이 루프 불변 조건은 다음과 같이 증명된다.

초기화: 루프가 처음으로 돌기 전에는 i = p - 1, j = p이므로 3개의 조건은 자동적으로 만족된다.

유지: A[j] > x이면 j가 1 늘어나는데 조건 2의 성립 여부는 변하지 않는다. A[j] \leq x이면 i가 1 늘어나고 A[i]A[j]가 뒤바뀐 뒤 j가 1 늘어난다. 값이 뒤바뀌기 때문에 A[i] \leq x가 되어 조건 1을 다시 만족하게 되고, A[j - 1]이 뒤바뀐 원소는 이전 루프 시점의 A[i + 1]이기 때문에 x보다 크게 되어 조건 2를 만족시킨다.

종료: 종료 시점에 j = r이 되어 모든 원소는 위의 3개 조건 중 하나를 만족시키게 되고, x 이하인 원소, x보다 큰 원소, x와 같은 원소의 3개로 분할된다.

PARTITION의 마지막 부분은 기준점을 올바른 위치로 옮겨서 전체 부분 배열이 정렬된 상태로 있게 함과 동시에 기준점의 새로운 위치를 반환한다. 수행 시간은 \Theta(r - p + 1)이다.

7.2. Performance of quicksort

퀵 정렬의 수행 시간은 분할이 균형을 이루는지 아닌지에 따라서 점근적 수행 시간이 병합 정렬 ~ 삽입 정렬만큼 달라질 수 있다.

Worst case partitioning

최악의 수행 시간은 분할할 때마다 부분 문제의 크기가 1개씩만 줄어들 때 일어난다. 이 때의 수행 시간은 T(n) = T(n-1) + \Theta(n)이 되어 T(n) = \Theta(n^{2})가 된다. 이것은 입력 배열이 완전히 정렬된 경우에 발생한다.

Best-case partitioning

최고의 수행 시간은 분할할 때마다 부분 문제의 크기가 절반씩 줄어들 때 일어난다. 이 때의 수행 시간은 T(n) = 2T(n/2) + \Theta(n)이 되어 T(n) = \Theta(n \lg n)이 된다.

Balanced partitioning

각각의 분할이 분할할 때마다 부분 문제의 크기가 상수 배씩 줄어든다면 그 상수가 몇이라도 수행 시간은 T(n) = \Theta(n \lg n)이다.

Intuition for the average case

평균적인 경우에 각각의 분할은 (수행 시간 면에서) 좋은 분할과 나쁜 분할로 배열을 나눈다. 나쁜 분할의 수행 시간은 점근적으로 전체 수행 시간에 흡수된다. 이것이 퀵 정렬의 평균 수행 시간이 우수한 이유이다.

7.3. A randomized version of quicksort

퀵 정렬을 포함한 여러 알고리즘은 입력을 무작위화해 성능 개선을 노릴 수 있다. 퀵 정렬에서는 무작위 샘플링을 사용하는데, 기준점을 항상 A[r]로 잡는 대신 A[p, \cdots, r]의 임의의 원소를 택하는 것이다.

RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)
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)

7.4. Analysis of quicksort

7.4.1. Worst-case analysis

최악의 경우에는 T(n) = \max_{0 \leq q \leq n - 1} (T(q) + T(n - q - 1)) + \Theta(n) 이 된다. 상수 c에 대해 T(n) \leq cn^{2}라 하면 T(n) \leq c \cdot \max_{0 \leq q \leq n - 1} (q^{2} + (n-q-1)^{2}) + \Theta(n) \leq c (n-1)^{2} + \Theta(n) \leq cn^{2}이어서 T(n) = O(n^{2})이다. 7.2장에서 T(n) = \Omega(n^{2})임을 보였으므로 T(n) = \Theta(n^{2})가 된다.

7.4.2. Expected running time

Running time and comparisons

QUICKSORT의 수행 시간은 PARTITION에 의존한다.

Lemma 7.1. QUICKSORT의 전체 실행 시간 동안 PARTITION에서 기준점 원소가 다른 원소와 비교되는 횟수를 X라 하면 QUICKSORT의 수행 시간은 O(n + X)이다.

X_{ij}z_{i}, z_{j}가 서로 비교되는지를 나타내는 지시확률변수라 하면 X = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} X_{ij}가 된다. \mathbb{E}[X] = \sum_{i=1}^{n - 1} \sum_{j = i + 1}^{n} \mathbb{E} [X_{ij}]인데, \mathbb{E} [X_{ij}]z_{i}, z_{j}가 서로 비교될 확률이다. 이를 어떻게 구할까?

기준점이 z_{i} < x < z_{j}로 선택될 경우 기준점보다 작은 집합과 기준점보다 큰 집합은 PARTITION 과정에서 서로 비교되지 않는다. 다시 말하면, z_{i}z_{j}z_{i}, \cdots, z_{j} 구간 내에 첫 기준점으로 선택될 경우 이는 해당 구간 내의 자신을 제외한 모든 원소와 비교되게 된다. 그러므로 z_{i}, z_{j}가 서로 비교될 확률은 둘 중 하나가 구간 내에 첫 기준점으로 선택될 확률과 같다. 이는 \frac{2}{j - i + 1}이다.

그러므로 \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} O(\lg n) = O(n \lg n)이다. 따라서 RANDOMIZED-PARTITION을 사용 시의 평균 수행 시간은 원소들이 전부 다를 때 O(n \lg n)이 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중