평균적으로 퀵 정렬은 머지보다, 빠른 것으로 알려져 있습니다. 물론 최악의 경우에, skew만 계속 일어나면, 별로 좋지는 않겠지만요. 이건 왜 그럴까요? 머지에 비해서 Quick은 추가적인 공간을 쓰지 않기 때문에 그렇습니다. 사실, 이게 제일 큰 요인입니다. 이것이 어떻게 동작하는지 이해가 가지 않으시다면, 관련 글을 보고 오시는 것도 좋겠습니다.
[관련글]
그러면 평균 복잡도는 왜 O(nlogn)일까요?
몇 가지 가정을 해 봅시다. partition이 일어날 때, arr[0]을 pivot으로 잡습니다. 이 때, 정렬을 할 데이터의 갯수가 n개라고 하면, arr[i]보다 작은 것의 갯수가 0개, 1개, 2개, ... , n-1개인 경우가 있을 거에요. 그러한 확률이 모두 1/n이라고 가정해 봅시다.
그런데 왜 하필 저리 가정을 할까요? 이유는 간단합니다. 배열 안에 중복된 데이터가 없다고 가정해 봅시다. 그러면 크기 순으로 정렬했을 때 0번째, ... , n-1번째 원소가 있을 겁니다.
set에는 n-1개의 원소가 있는데요. 이 중에서 0을 택하면, 0보다 작은 원소는 0개입니다. 1을 택한다면, 1보다 작은 원소는 1개일 거에요. n-1을 택한다면? n-1보다 작은 것의 갯수는 n-2개가 아닐까요? 이 수들이 골고루 분포가 되어 있다면, 0을 선택할 확률이나, 1을 선택할 확률이나, n-1을 선택할 확률은 모두 같습니다.
1/n으로 말입니다. 따라서, 1/n으로 잡습니다. 물론, 중복된 데이터가 들어올 수도 있을 겁니다. 그런데 데이터를 랜덤하게 돌려보면, 중복된 데이터들이 매우 많이 들어올 확률은 생각보다 드물고, 설령 들어왔다고 하더라도, n진법 시스템을 이용해서 적당히 변환해 주면 중복 처리를 할 수 있어요.
그러니, 중복 데이터는 고려하지 않겠습니다.
array가 있습니다.
배열 arr이 있습니다. 저는 여기서 피벗값을 arr[0]으로 잡았습니다.
그러면 보라색을 기준으로 보라색 원소보다 작은 것과, 크거나 같은 것으로 분류를 할 수 있습니다.
그러면, arr[0]보다 큰 게 n-1개인 경우가 있습니다. 이 때에는 n-1개의 부분 array를 sorting 해야 합니다.
이 경우에는 어떤가요? arr[0]보다 작은 것이 1개, 큰 것이 n-2개 있습니다. 그러면 노란 부분도 sort를 해야 하고, 초록색 부분도 sorting을 해야 할 거에요. 즉, 이 때에는 배열의 전체를 돈 다음에 T(1) + T(n-2)만큼의 연산을 수행해야 합니다.
이 때에는 어떤가요? 노란 부분의 갯수는 2개, 초록색 부분의 갯수는 n-3개입니다.
그러면 이 경우에는 1/n의 확률로 배열 전체를 돌고, T(2) + T(n-3)만큼의 연산을 수행해야 겠네요.
그런데, 실제로 n개짜리 배열에서 arr[0]을 기준 값으로 잡으면 노란색 부분만 돌면 됩니다. 그렇기 때문에, n-1개의 원소만 보면 됩니다. 정렬할 배열의 크기가 n이고, 피벗보다 작은 값이 x개 있을 확률을 1/n이라고 했을 때, 다음 관계식이 성립합니다.
T(n) = 2(T(0) + ... + T(n-1))/n + (n-1)
이 수식을 어떻게 잘 정리할 필요가 있겠네요.
일단 기저 조건 먼저 봅시다. 만약에 배열의 크기가 1입니다.
이 때에는 굳이 정렬할 필요가 있을까요? 없습니다. 따라서 T(1) = 0이라고 할 수 있습니다. 그러면 T(n)을 어떻게 구하면 좋을까요? 위에 수식은 분수가 있으니 너무 지저분해 보입니다. 분수를 없앱시다.
nT(n) = 2(T(0) + ... + T(n-1)) + n(n-1)
그러면 이걸 가지고 무엇을 하면 좋을까요? (n-1)T(n-1)도 구해보면 좋지 않을까요?
(n-1)T(n-1) = 2(T(0) + ... + T(n-2)) + (n-1)(n-2)
이 두 식을 빼 봅시다. 그러면 nT(n) - (n-1)T(n-1)의 값이 2T(n-1) + 2(n-1)임을 알 수 있어요. 이걸 적절히 변형시키면 무엇인가 나올 거 같은데요. 이걸 잘 정리해 보면 nT(n)과, (n+1)T(n-1) + 2(n-1)이 같다는 것을 알 수 있어요. n(n+1)로 양 변을 나눠 봅시다.
T(n)/(n+1) = T(n-1)/n + 2(n-1)/(n(n+1))
이 수식을 보아하니 뭔가 나올 거 같은데요. 1/(n(n+1))은 1/n - 1/(n+1)과 같습니다. 이를 이용하면 위의 수식은, 다음과 같이 바꿀 수 있습니다.
T(n)/(n+1) = T(n-1)/n + 2(n-1)/n - 2(n-1)/(n+1)
이제 대치법을 쓸 수 있겠네요. T(n-1)/n을 같은 방법으로 바꾸면 T(n-2)/(n-1) + 2(n-2)/(n-1) - 2(n-2)/n입니다. 그러면 위의 수식을 아래와 같이 바꿔서 쓸 수 있습니다.
T(n)/(n+1) = T(n-2)/(n-1) + 2(n-2)/(n-1) - 2(n-2)/n + 2(n-1)/n - 2(n-1)/(n+1)
이것을 이제 T(n-3)에 관한 식으로 정리해 봅시다.
T(n)/(n+1) = T(n-3)/(n-2) + 2(n-3)/(n-2) - 2(n-3)/(n-1) + 2(n-2)/(n-1) - 2(n-2)/n + 2(n-1)/n - 2(n-1)/(n+1)
이런 식으로 쭉 정리를 해서, T(n)/(n+1)을 T(1)에 관한 식으로 바꿔 보면, 아래와 같습니다.
T(n)/(n+1) = T(1)/2 + 2/2 + 2/3 + ... + 2/n - 2(n-1)/(n+1)
여기서 노란색으로 칠한 부분은, 동류항끼리 묶어서 계산한 거에요. 그러면 노란색은 2(1/2+...+1/n)으로 나타낼 수 있어요. 그러면 이것의 값이 어떻게 나오나 보아야 할 건데요.
1/2 + 1/3 + ... + 1/n 를 나타낸 겁니다. 이 직사각형들의 넓이의 합은 1/2 + ... + 1/n입니다. 이것은 x=2부터 n+1까지 1/x의 적분값보다는 큽니다. 하지만, 이 직사각형들을 각각 x축으로 -1만큼 평행이동 시키면 이야기가 달라집니다.
x=1부터 n까지 1/x의 적분값보다는 작습니다. 즉, 1/2 + ... + 1/n은 ln(n)보다는 작고, ln(n+1) - ln(2)보다는 크다는 겁니다. ln(x)급인 건 부정 못하겠군요. 즉, T(n)/(n+1)은 2ln(n) + ... 꼴이라는 겁니다. 상수는 n이 매우 크다면, ln(n)에 비해서 매우 작기 때문에 무시해도 됩니다.
이를 T(n)에 대해 다시 정리하면 T(n)은 2(n+1)ln(n) + ... 꼴이므로 nln(n) + ... 꼴이 되는데요. 밑이 2인 로그로 바꾸면, 앞에 상수가 1.4가 붙습니다. merge sort가 임시 공간에 복사하고, 다시 원래 공간에 복사하고, 두 개의 부분 배열을 비교하는 그러한 것까지 고려했을 때 2.x ~ 3, 데이터 사이즈가 더 커지면 cache도 잘 못 쓸 겁니다. 그런 것까지 고려를 하면, 평균적으로 상수도 작고 속도도 빠르다는 것을 알 수 있어요. 다만, 최악의 경우에 skew가 되면 그 경우에, 복잡도가 n^2가 되기 때문에 정렬 알고리즘을 직접 구현해야 하는 상황에서는 merge를 많이 고려하는 편입니다.
'자료알고 > 알고리즘' 카테고리의 다른 글
| 중복 조합 : 어떻게 ps에서 쓰일까요? (3) | 2019.08.24 |
|---|---|
| 왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까? (2) | 2019.08.21 |
| k번째 수 찾기 : count sort를 응용해 봅시다. (2) | 2019.08.17 |
| 양방향 탐색 : 시작점과 도착점에서 동시에 탐색을 한다. (5) | 2019.08.16 |
| 퀵 정렬 : bad partition이 발생할 경우 문제가 된다. (4) | 2019.08.15 |
최근댓글