QuickSort
Quick Sort는 Merge Sort와 비슷하게, 아래와 같이 분할 정복을 사용한다.
Divide : 배열 A[p..r]을 A[p..q-1]과 A[q+1..r]로 나눈다.
Conquer : 재귀를 이용해서 배열A[p..r]과 A[q+1..r]에 대해서 Quick Sort를 시행한다.
Combine : 서브 배열들이 이미 정렬된 관계로 딱히 합칠 필요는 없다.
그리고 이는 아래와 같은 의사 코드로 표현해 낼 수 있다.
// Let A -> matrix and p,r -> index
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[j]
return i+1
QuickSort(A, p, r)
if p<r
q = Partition(A, p, r)
Quicksort(A, p, q-1)
Quicksort(A, q+1, r)
QuickSort(A, 1, A.length)대충 하나를 Pivot으로 잡아서 서브어레이를 만들어 내고, 정렬을 때린 다음 다시 서브 어레이를 돌린다고 생각하면 된다.
이는 Big-O Notation으로 표기했을때 NLogN~N^2 정도의 시간 복잡도를 보이게 된다. 정확히는, QuickSort의 정렬 시간은 서브 어레이 분할이 적절히 균등한지(balanced) 아닌지에 따라 달려있다.
일단 최악의 경우/최선의 경우/균형잡힌 경우로 생각해보자. 먼저 최악의 경우는 서브 어레이를 0개/n-1개로 나누는 경우를 의미한다. 만약 이게 재귀 호출을 때릴때 마다 일어난다고 생각하면... O(N^2)에 시간복잡도가 수렴할 것임을 생각할 수 있다. 참고로 이랑 비슷한 case는 이미 정렬되어 있는 배열에 Quick Sort를 갈길 때 이다. 그리고 최선의 경우/균형잡힌 경우에는 T시간 복잡도가 O(NLogN)에 다다르게 된다.
참고로 Quicksort의 실행시간이 얼마나 걸릴지 대걍 짐작해 볼 수 있는 거시기가 있다. Quicksort가 와다다다 하고 서브어레이를 만들어 내면 그 분할이 Balanced 할 수도 있고 아닐 수도 있을 것이다. 즉슨 "평균적으로는" Balanced 된 얘가 적절하던 아니던 할 것이고 - unBalanced한 경우 뒤에 Balanced한 경우가 붙으면 Big-O Notation은 O(N)이 된다. 그러니까 Unbalanced한 상황은 묻히게 되어 버릴 것이며, 따라서 평균적인 경우에도 O(NLogN)에 다다르게 된다.
근데 이건 이론이 그렇다는거고 엔지니어링 관점에선 아니다! 그래서 Random Sampling을 통해서 A[r]대신 다른 친구를 pivot으로 갈긴다.
※ 시간 복잡도에 대한 상세한 증명은 아래와 같다.
▶ 최악의 경우
앞에서도 이야기 했다 싶이 Wort-case에는 time-complexity가 O(N^2)에 수렴하게 되는데... 쨋든 T(n)이 input size n에 대한 최악의 시간이라고 해보자, 그러면
이 된다. 이때 T(n)은 어떤 상수 C에 대해서 T(n) <= Cn^2이라고 생각해 볼 수 있으므로 위 식은 아래와 같이 표현할 수 있겠다.
이때 q^2 + (n-q-1)^2은 q=0 or q=n-1에서 최대가 된다. 따라서 이걸 감안하면 T(n) <= Cn^2가 된다. c(2n-1)에서 c가 충분히 나락으로 가면 theta(n)을 잡아먹기 때문. (Theta Notation과 Big-O Notation은 구분해 주도록 하자.)
▶ 평균적인 경우
상한선/하한선을 지지고 볶을 수는 있는데, 일단 앞에서 얘기했다 싶이 최선의 경우/균형 잡힌 경우에는 시간 복잡도가 O(NLogN)에 다다르게 된다. 증명은 음.. 생략하자.