아직 퀵 정렬이 무엇인지 모른다면 여기로

🚨 이번 포스트는 복잡한 식과 머리 아픈 내용이 나올 수 있습니다. (제 기준)

퀵 정렬의 성능

저번 포스트에서는 퀵 정렬에 대해 알아보았다. 퀵 정렬의 평균적인 수행시간이 O(n log n) 이고 최악의 수행시간이 O(n^2) 이라는 것을 알았지만 최악의 수행시간이 O(n^2) 이나 되는 알고리즘이 어째서 힙 정렬보다 더 빠른지에 대해서는 자세히 다루지 않았다. 이번 포스트에서는 퀵 정렬의 성능에 대해 알아보고 어째서 퀵 정렬이 힙 정렬보다 더 효율적인 알고리즘인가에 대해 알아볼 것이다.

퀵 정렬의 수행시간은 분할 후 양쪽 구역의 크기가 비슷한가 아닌가에 따라 달라진다. 분할이 균등하게 된다면 퀵 정렬은 병합 정렬처럼 빠르게 작동한다. 하지만 분할의 균등하지 않다면 삽입 정렬처럼 느리게 동작한다.

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

퀵 정렬에서 최악의 경우는 분할과정에서 원래의 문제를 원소가 n-1개인 배열과 0개짜리인 배열로 나눌때이다. 재귀 호출을 할 때마다 이런 불균등 분할이 일어난다고 가정하면 분할 과정에서 O(n) 시간이 소요되고 크기가 0인 배열에 대한 재귀호출은 결과가 즉시 리턴되므로 T(0) = O(1)이다. 따라서 수행시간에 대한 재귀 관계식은 다음과 같다.

T(n) = T(n - 1) + T(0) + O(n) // T(0)은 O(1)과 같기에 없어진다.
= T(n - 1) + O(n)

직관적으로 각 재귀 호출 단계에서 발생하는 비용을 모두 더하면 O(n^2) 가 나온다. 실제로 치환법을 사용하면 T(n - 1) + O(n) 이 식의 해가 T(n) = O(n^2)임이 증명된다. 따라서 모든 재귀 호출에서 분할이 불균등하게 이루어진다면 수행시간은 O(n^2)이 된다. 하지만 애초에 모든 분할이 불균등하게 이루어진다는 것이 쉽지 않고 그렇게 되는 경우는 배열의 거의 정렬된 상태이기 때문에 삽입 정렬을 사용한다면 O(n) 시간에 정렬이 가능하다.

분할을 가장 잘하는 경우

분할이 가장 잘 된 경우는 Partition이 생성하는 부분 문제 두 개의 크기가 각각 [n / 2]과 [n / 2] - 1 이 되어 양쪽 모두 크기가 n/2 이하인 경우이다. (정확하게 절반으로 나눈 경우) 이 경우 퀵 정렬이 아주 빠르게 동작한다. 이때 수행시간에 대한 재귀 관계식은 다음과 같다.

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

마스터 정리의 두 번째 경우에 따라 이 식의 해는 T(n) = O(n lg n) 이다. 따라서 재귀 호출을 할 때마다 항상 분할이 균등하게 된다면 알고리즘도 빠르게 동작한다.

균등 분할

퀵 정렬의 평균 수행시간은 최악의 경우 O(n^2) 보다 최적인 경우 O(n log n)에 가깝다.

예를 들어, 분할 알고리즘이 문제를 항상 9대 1로 분할하는 경우를 생각해보자. 언뜻 보기에는 매우 불균등하게 보이지만 이 경우 수행시간에 대한 재귀 관계식은 다음과 같이 된다.

T(n) ≤ T(9n / 10) + T(n / 10) + cn

위 식에서는 깊이가 O(log n) 에 이를 때까지는 트리의 각 레벨에서 사용하는 비용이 cn 이고 그 다음부터는 cn 보다 작거나 같다. 재귀는 깊이 O(log n) 에서 끝난다. 그러므로 퀵 정렬의 비용은 O(n log n) 이 된다. 즉 직관적으로는 굉장히 불균등하게 보이지만 매 재귀 단계에서 분할이 9대 1 비율로 이루어진다면 퀵 정렬은 O(n log n) 시간에 동작한다. 이는 분할이 계속 일정한 비율로만 이루어진다면 재귀 트리의 깊이가 O(log n)이고 각 레벨의 비용이 O(n)이기 때문에 수행시간은 O(n log n) 이 된다.

평균적인 경우?

퀵 정령이 임의의 배열에 대해 동작할 때는 위에서 가정한 것처럼 분할이 매 단계마다 똑같은 비율로 일어날 가능성은 거의 없다. 어떤 분할은 균등하게 되고, 또 어떤 분할은 균등하지 않게 될 수도 있다.

평균적인 경우, Partition 결과 중에는 균등하게 나뉜 분할과 균등하지 않게 나뉜 분할이 섞여 있다. 만약 최적의 분할과 최악의 분할이 번갈아 나오는 상황을 가정한다면 먼저 루트에서 분할 비용은 n이 되고 그 다음으로 생성되는 부분 배열은 n - 1과 0으로 최악의 경우가 된다. 다음 레벨에서는 n - 1인 부분 배열이 각각 (n - 1) / 2 - 1 과 (n - 1) / 2인 두 부분 배열로 분할된다. 최악의 경우 이후에 최적의 경우가 이어지는 조합은 크기가 각각 0, (n - 1) / 2 - 1, (n - 1) / 2 - 1 인 세 부분 배열을 만들고, 비용은 O(n) + O(n - 1) = O(n) 만큼 든다. 또한 최악의 경우의 O(n - 1) 은 최적의 경우의 비용 O(n) 에 흡수될 수 있으므로 결과적으로 최악의 경우와 최적의 경우가 번갈아 일어날 경우에 수행시간은 O(n log n) 으로 최적의 경우와 비슷하다.

다만 이 경우 숨겨진 상수는 조금 더 커진다.

결론

이번 포스트에서는 퀵 정렬의 성능에 대해 알아보았다. 확실히 이러한 이론은 재미는 없지만 쓸데는 많은 것 같다. 다음 포스트에서는 랜덤화된 퀵 정렬에 대해 알아보고 랜덤화된 퀵 정렬의 수행시간에 대해 알아보자.