퀵소트의 시간 복잡도 구하기

퀵소트란?

퀵소트(Quick Sort)란 피벗을 활용한 정렬 알고리듬입니다. 정렬 알고리듬이란, 순서가 맞지 않는 배열이 주어졌을 때 이를 정해진 순서대로 나열하는 함수를 말합니다. 이 글에서는 피벗을 정렬에 어떻게 활용하는 것인지 살펴보고, 이를 토대로 퀵소트의 시간 복잡도를 수학적으로 증명해봅니다.

퀵소트 알고리듬

퀵소트의 핵심 아이디어는 피벗을 기준으로 배열을 둘로 나누고, 각각의 부분 배열에 재귀적으로 퀵소트를 호출한 다음 순서대로 합치는 것입니다. 분할 정복(Divide and Conquer)이라고 부르는 전략인데요, 간단한 예를 통해 살펴보도록 하겠습니다.

퀵소트의 동작

퀵소트의 예시

다음과 같이 5개의 숫자를 가진 배열을 정렬한다고 가정합시다.
quick_sort([3, 2, 4, 5, 1])

우선 이를 둘로 나누기 위해서 피벗을 첫 번째 원소인 3으로 정합니다. 그리고 배열을 이 피벗 보다 작은 수와, 그렇지 않은 수로 나눕니다.
[2, 1], [4, 5]

각각에 대하여 퀵소트를 재귀 호출합니다.

quick_sort([2, 1])

첫 번째 원소인 2를 피벗으로 정하고, 배열을 나눕니다.
[1], []

이 둘에 대해서도 퀵소트를 호출하지만, 개수가 1개인 경우 그대로 값을 리턴합니다. 정렬된 결과 값과 피벗 ([1], 2, []) 을 순서대로 합친 배열을 반환합니다.
[1, 2] \cdots (1)

quick_sort([4, 5])

첫 번째 원소인 4를 피벗으로 정하고, 배열을 나눕니다.
[], [5]

이 둘에 대해서도 퀵소트를 호출하지만, 개수가 1개인 경우 그대로 값을 리턴합니다. 정렬된 결과 값과 피벗 ([], 4, [5]) 을 순서대로 합친 배열을 반환합니다.
[4, 5] \cdots (2)

앞서 두 재귀 호출에서 얻어진 값 (1), (2)와 피벗인 3을 순서대로 합친 배열을 반환합니다
[1, 2, 3, 4, 5]

퀵소트 알고리듬

앞서 살펴 본 예시에서 배열을 나누는 과정을 partition()이라는 함수로 정의하면, 아래와 같은 파이썬 코드로 작성할 수 있습니다 (통상적으로 퀵소트는 in-place 알고리듬으로 구현하지만, 이 글에서는 이해를 돕기 위해 매번 새 배열을 생성하는 알고리듬을 소개합니다).

def quicksort(A):
if len(A) <= 1:
return A
left, pivot, right = partition(A)
return quicksort(left) + [pivot] + quicksort(right)
def partition(A):
pivot = A.pop(0)
left, right = [], []
for a in A:
if a < pivot:
left.append(a)
else:
right.append(a)
return left, pivot, right

퀵소트에서는 partition()에서 어떤 기준으로 피벗을 선택하느냐에 따라 quicksort()의 재귀 호출이 되는 left, right의 크기가 달라지는데요. 때문에 최악의 경우 원소 개수 만큼 재귀호출을 하게 됩니다. 예를 들어 [1, 2, 3, 4, 5]라는 배열을 맨 첫 번째 원소를 피벗으로 정하는 경우 아래 그림과 같이 재귀 호출이 일어납니다.

최악의 경우 퀵소트의 예시

이런 경우를 막기 위해 피벗을 정하는 다른 전략이 필요합니다. 가장 손쉬운 방법은 바로 ‘임의의 원소’를 피벗으로 택하는 것입니다. 이 경우, 재귀 호출의 수는 평균적으로 O(nlogn)O(n\log{n})이 됩니다. 평균적인 시간 복잡도의 의미와 그 수학적 증명을 위해서 몇 가지 수학적 개념을 살펴봅시다.

수학 돌아보기

확률

확률이란 특정한 사건이 일어날 가능성을 실수로 나타낸 것입니다. 수학적으로는 다음과 같이 정의할 수 있습니다.

표본 공간(Sample Space) SS: 일어날 수 있는 모든 경우의 집합

사건 ff: 특정한 사건에 해당하는 경우들(표본 공간의 부분 집합, fSf \subseteq S)

사건의 집합 FF: 사건들의 집합

이때 PP는 사건들의 집합을 확률로 대응시키는 함수입니다. P:FRP:F \rarr \R

예를들면, 1부터 6까지 적혀있는 주사위 하나를 던질 때 눈이 1 혹은 2가 나오는 사건들의 확률은 다음과 같이 구할 수 있습니다.

S={s1,s2,s3,s4,s5,s6}F={{s1},{s2}}P(F)=n(F)n(S)=1/3\begin{aligned} & S = \{ s_1, s_2, s_3, s_4, s_5, s_6 \} \\ & F = \{ \{s_1\}, \{s_2\} \} \\ & P(F) = {n(F) \over n(S) } = 1 / 3 \end{aligned}

여기서 S 집합의 원소를 s1, s2, , s6s_1,\ s_2,\ \cdots,\ s_6 로 표현했는데요. 이 의미는 (던져서 1이 나오는 경우), (던져서 2가 나오는 경우), \cdots 와 같이 하나의 경우를 의미합니다.

확률 변수

확률 변수(Random Variable)는 특정한 사건들에 대하여 대응되는 변수 값을 갖는 함수(X:FSX: F \rarr S)를 말합니다.

예를들어 두 개의 동전을 던졌을 때 앞면인 동전의 수를 확률 변수 XX라고 정의해봅시다. 이때 표본 공간을 SS, 0개일 사건들 F0F_0, 1개일 사건들 F1F_1, 그리고 2개일 사건들의 집합을 F2F_2라고 합시다. 이때의 확률 변수는 다음과 같이 정의됩니다.

S={ (Head,Head), (Head,Tail), (Tail,Head), (Tail,Tail) }F0={ (Tail,Tail) }F1={ (Head,Tail), (Tail,Head) }F2={ (Head,Head) }X(F0)=0X(F1)=1X(F2)=2\begin{aligned} & S = \{\ (Head,Head),\ (Head, Tail),\ (Tail, Head),\ (Tail, Tail )\ \} \\ & F_0 = \{\ (Tail, Tail)\ \} \\ & F_1 = \{\ (Head, Tail),\ (Tail, Head)\ \} \\ & F_2 = \{\ (Head, Head )\ \} \\ & X(F_0) = 0 \\ & X(F_1) = 1 \\ & X(F_2) = 2 \\ \end{aligned}

따라서 확률 변수 X에 대하여, X의 값이 1일 때의 확률은 다음과 같이 구할 수 있습니다.

Pr(X=1)=P(F1)=P({ (Head,Tail), (Tail,Head) })=n(F1)/n(S)=2/4=1/2\begin{aligned} & Pr(X = 1) \\ & = P(F_1) \\ & = P(\{\ (Head, Tail),\ (Tail, Head)\ \}) \\ & = n(F_1) / n(S) \\ & = 2 / 4 = 1 / 2 \\ \end{aligned}

기대값과 기대값의 선형성

확률 변수의 기대값(Expectation)이란 확률 변수의 가중된 평균값을 의미합니다. 여기서 가중은 확률을 통해 가중된다는 의미입니다. 가능한 모든 확률 변수 값에 대하여 확률을 가중치로 두고 평균을 구하는 것이죠. 이를 수학적으로 표현하면 다음과 같습니다.

E[X]=xxPr(X=x)E[X] = \sum_{x}x \cdot Pr(X=x)

평균이라는 말이 어색하다면, Pr(X=x)Pr(X=x)의 값이 항상 1/n1 / n 인 경우 (nn은 가능한 모든 확률 변수의 개수) 를 생각해보면 이것이 어째서 가중 평균인지 이해할 수 있을 것입니다.

기대값에는 선형성(Linearity)이라는 성질이 있습니다. 즉, 두 확률 변수 XX, YY에 대하여 다음이 성립합니다.

E[X+Y]=E[X]+E[Y]E[X + Y] = E[X] + E[Y]

예를들어 앞서 두 개의 동전을 던지는 예를 살펴 보겠습니다. 동전들의 순서쌍에서 첫 번째 동전이 앞면인 수를 확률 변수 X, 두 번째 동전이 앞면인 수를 Y라고 정합니다.

Pr(X=0)=P({ (Tail,Head), (Tail,Tail) })=1/2Pr(X=1)=P({ (Head,Head), (Head,Tail) })=1/2E[X]=0(1/2)+1(1/2)=1/2Pr(Y=0)=P({ (Head,Tail), (Tail,Tail) })=1/2Pr(Y=1)=P({ (Head,Head), (Tail,Head) })=1/2E[Y]=0(1/2)+1(1/2)=1/2\begin{aligned} & Pr(X = 0) = P(\{\ (Tail, Head),\ (Tail, Tail)\ \}) = 1 / 2\\ & Pr(X = 1) = P(\{\ (Head, Head),\ (Head, Tail)\ \}) = 1 / 2\\ & E[X] = 0 * (1 / 2) + 1 * (1 / 2) = 1 / 2\\ & Pr(Y = 0) = P(\{\ (Head, Tail),\ (Tail, Tail)\ \}) = 1 / 2\\& Pr(Y = 1) = P(\{\ (Head, Head),\ (Tail, Head)\ \}) = 1 / 2\\ & E[Y] = 0 * (1 /2) + 1 * (1 / 2) = 1 / 2\\ \end{aligned}Pr(X+Y=0)=P({ (Tail,Tail) })=1/4Pr(X+Y=1)=P({ (Head,Tail), (Head,Tail) })=1/2Pr(X+Y=2)=P({ (Head,Head) })=1/4E[X+Y]=0(1/4)+1(1/2)+2(1/4)=1\begin{aligned} & Pr(X + Y = 0) = P(\{\ (Tail, Tail)\ \}) = 1 / 4\\ & Pr(X + Y = 1) = P(\{\ (Head, Tail),\ (Head, Tail)\ \}) = 1 / 2\\ & Pr(X + Y = 2) = P(\{\ (Head, Head)\ \}) = 1 / 4\\ & E[X + Y] = 0 * (1 / 4) + 1 * (1 / 2) + 2 * (1 / 4) = 1\\ \end{aligned}

이는 동일한 확률 공간 내의 어떠한 확률 변수에 대해서도 성립하는 성질입니다.

퀵소트의 시간 복잡도 구하기

이제 다시 퀵소트로 돌아와 시간 복잡도를 구해봅시다.

퀵소트의 최종 결과가 [Z1, Z2, , ZnZ_1,\ Z_2,\ \cdots,\ Z_n]라고 할 때,

표본 공간 SS가 피벗을 정하는 경우의 수인 확률 공간을 생각해봅시다. sis_iZiZ_i를 피벗으로 정하는 경우를 말합니다.

S={s1, , sn}S = \{ s_1,\ \cdots,\ s_n \}

확률 변수 Xi,jX_{i,j}ZiZ_iZjZ_j가 비교된 횟수라고 합시다. 그렇다면 우리가 구하고자 하는 평균 시간 복잡도는 이 비교된 횟수들의 합의 기대값을 통해 구할 수 있을 것입니다. 즉, 총 비교 횟수를 확률 변수 CC라고 한다면 아래와 같이 나타낼 수 있습니다.

C=in1j=inXi,jC = \sum_{i}^{n-1}\sum_{j=i}^{n}X_{i,j}

따라서 그 기대값은 기대값의 선형성에 의해 다음과 같이 구할 수 있습니다.

E[C]=E[in1j=inXi,j]=in1j=inE[Xi,j]\begin{aligned} E[C] {}={} & E[\sum_{i}^{n-1}\sum_{j=i}^{n}X_{i,j}] \\ {}={} & \sum_{i}^{n-1}\sum_{j=i}^{n}E[X_{i,j}] \\ \end{aligned}

그런데 E[Xi,j]E[X_{i,j}] 의 값은 어떻게 될까요? 퀵소트에서는 두 수가 비교되는 횟수는 최대 1번 입니다. 이때 두 숫자는 같은 재귀 호출에서 호출되고, 둘 중 한 숫자가 피벗으로 선택되어야 비교됩니다. 기대값을 구하기 위해서 필요한 것은 오로지 비교되는 경우의 확률이므로, ZiZ_iZjZ_j 가 같은 재귀 호출에 호출되는 경우만을 고려해 봅시다.

ZiZ_{i}ZjZ_{j}가 같은 재귀 호출에 존재하려면, 반드시 [Zi,Zj][Z_i, Z_j]구간의 모든 원소가 같은 재귀 호출에 존재해야 합니다. (만일 상위 호출에서 이 구간이 쪼개졌다면, ZiZ_iZjZ_j는 같은 호출에 존재할 수 없습니다)

이 경우 임의로 피벗을 선택하면 각 원소가 피벗으로 선택될 확률 ppp1/(ji+1)p \leq 1/(j - i + 1) 으로 동일할 것입니다. 따라서 이를 토대로 기대값을 구하면,

Pr(Xi,j=1)=2(ji+1)E[Xi,j]=0Pr(Xi,j=0)+1Pr(Xi,j=1)12(ji+1)=2(ji+1)\begin{aligned} Pr(X_{i,j} = 1){}={}& {2 \over (j - i + 1)} \\ E[X_{i, j}]{}={}& 0 * Pr(X_{i,j} = 0) + 1 * Pr(X_{i,j} = 1)\\ {}\leq{}& 1 * { 2 \over (j - i + 1) } \\ {}={}& {2 \over (j - i + 1)} \end{aligned}

이것을 사용해서 앞서 구한 두 수를 비교한 횟수의 기대값인 E[C]E[C]를 구해보면,

E[C]in1j=in2(ji+1)2injn1(j+1)=2njn1(j+1)<2nlnn=(2loge)nlogn\begin{aligned} E[C]{}\leq{}& \sum_{i}^{n-1}\sum_{j=i}^{n}{2 \over (j - i + 1)} \\ {}\leq{}& 2 * \sum_{i}^{n}\sum_{j}^{n}{1 \over (j + 1)} \\ {}={}& 2 * n\sum_{j}^{n}{1 \over (j + 1)} \\ {}\lt{}& 2 * n \ln{n} = ({ 2 \over \log{e} }) * n \log{n} \end{aligned}

퀵소트의 시간 복잡도가 E[C]E[C]에 비례하여 늘어난다고 할 때, 시간 복잡도를 다음과 같이 구할 수 있습니다. (KK는 상수)

n1, T(n)=KE[C]<Knlogn\forall n \geq 1,\ T(n) = K * E[C] \lt K' * n \log{n}

따라서 퀵소트는 피벗을 임의로 랜덤하게 선택할 때 평균적으로 O(nlogn)O(n \log{n}) 의 시간 복잡도라고 할 수 있습니다.

참고자료