[Introduction to Algorithms] 퀵 정렬 - 퀵 정렬의 성능

1) 개요

- 퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한지 그렇지 않은지에 따라 달라지고,

  분할의 균형도는 분할할 때마다 어떤 기준 원소를 사용하는지에 달려 있다.

  분할이 균등하게 되면 퀵 정렬은 (점근적으로) 병합 정렬처럼 빠르게 동작한다. 

  그러나 균등하지 않다면 삽입 정렬처럼 느리게 동작한다.

  이 글에서는 분할이 균등하게 또는 불균등하게 이루어질 때 퀵 정렬의 성능이 어떻게 되는지를 

  약식으로 조사한다.

 

 

2) 분할을 가장 나쁘게 하는 경우 

- 퀵 정렬에서 최악의 경우는 분할과정에서 원래의 문제를 n-1개 짜리와 0개 짜리 부분 문제로 나누는 때다.

  재귀 호출을 할 때마다 이런 불균등 분할이 발생한다고 가정해보자.

  분할 과정에 소요되는 시간은 O(n)이다. 

  크기가 0인 배열에 대한 재귀 호출은 결과가 즉시 리턴되므로 T(0) = O(1)이다.

  따라서 수행시간에 대한 재귀 관계식은 다음과 같다. 

T(n) = T(n-1) + T(0) + O(n)
     = T(n-1) + O(n)

 

- 직관적으로 각 재귀 호출 단계에서 발생하는 비용을 모두 더하면 O(n2)인 등차 급수를 얻는다.

  실제로 치환법을 사용하면 재귀 관계식 T(n) = T(n-1) + O(n)의 해가 

  T(n) = O(n^2)임이 간단하게 증명된다. 

 

- 따라서 모든 재귀 호출에서 분할이 가장 불균등하게 이루어지면 수행시간은 O(n^2)이 된다.

  그러므로 퀵 정렬의 최악의 경우 수행시간은 고작해야 삽입 정렬 수준이다.

   게다가 O(n^2)이라는 수행시간은 입력 배열이 거의 완전히 정렬되어 있을 때 일어나는데,

   삽입 정렬을 이용하면 오히려 대부분의 경우에 O(n) 시간에 정렬이 가능하다. 

 

3) 분할을 가장 잘하는 경우

- 가장 고른 분할은 PARTITION의 생성하는 부분 문제 두 개의 크기가 각각 [n/2]과 [n/2]-1이 되어

  양쪽 모두 크기가 n/2이하인 경우다. 이 경우 퀵 정렬이 아주 빠르게 동작한다.

  상한과 하한 함수, -1과 같은 상수항을 무시한다면 수행시간에 대한 재귀 관계식은 다음과 같다. 

T(n) = 2T(n/2) + O(n)

 

- 마스터 정리의 두 번째 경우에 따라 이 식의 해는 T(n) = O(nlgn)이다.

  따라서 재귀 호출을 할 때마다 항상 분할이 균등하게 이루어진다면, 

  알고리즘도 (점근적으로) 빠르게 동작한다. 

 

4) 균등 분할

- 퀵 정렬의 평균 수행 시간은 최악의 경우보다는 최적인 경우와 가깝다.

  이를 이해하기 위한 핵심 요소는 분할의 균형 정도가 수행시간을 나타내는 관계식에

  어떻게 반영되는지를 알아보는 것이다. 

 

- 예를 들어, 분할 알고리즘이 문제를 항상 9대 1로 분할하는 경우를 생각해보자.

   언뜻 보기에는 매우 불균등하게 보이지만 이 경우 퀵 정렬의 수행시간에 대한 재귀 관계식은 다음과 같다. 

T(n) <= T(9n/10) + T(n/10) + cn

 

- 위 식에서 O(n) 항에 숨겨진 상수 c를 명시적으로 포함시켰다.

  그림 7.4는 이 재귀 관계식에 대한 재귀 트리를 보여준다. 

  깊이가 logn = O(lgn)에 이를 때까지는 트리의 각 레벨에서 사용하는 비용이 cn이고,

  그 다음부터는 cn보다 작거나 같다. 재귀는 깊이 logn = O(lgn)에서 끝난다. 

  그러므로 퀵 정렬의 비용은 O(nlgn)이다. 

 

- 즉, 직관적으로 매우 불균등하게 보이지만, 매 재귀 단계에서 분할이 9대 1 비율로 이루어진다면

  퀵 정렬은 점근적으로는 정확하게 절반으로 분할할 때처럼 

  O(nlgn) 시간에 동작한다

 

- 심지어 99대 1로 분할하더라도 O(nlgn)이란느 수행시간이 나온다.

  이는 분할이 계속 일정한 비율로만 이루어진다면

  재귀 트리의 깊이가 O(lgn)이고 각 레벨의 비용이 O(n)이기 때문이다. 

  따라서 분할이 일정한 비율로만 이루어진다면 수행 시간은 O(nlgn)이다.