[Algorithm] Sorting (Quick sort)

앞서 분할 정복 알고리즘의 예시 중에는 퀵 정렬도 있었는데, 이번 시간에는 퀵 정렬에 대해 알아보려고 한다. 우리는 계속해서 더 나은 Complexity를 가진 알고리즘을 알아보고 있기 때문에 퀵 정렬의 장·단점 또한 알아두는 것이 중요할 것이다.

 

pros and cons

 

앞으로 다룰 정렬에는 더 나은 복잡도가 있을지도 모르겠다 (아직 공부 중이므로 알 수 없다). 하지만 퀵 정렬의 경우 앞서 살펴본 병합, 힙 정렬처럼 일반적으로 $\Theta(n·\log{n})$의 시간 복잡도를 가지며, 추가적인 메모리 공간이 필요하지 않은 in-place 알고리즘에 속한다. 그러나 다른 알고리즘과 다른 특이한 점은 퀵 정렬의 경우 최악의 상황에서는 $\Theta(n^{2})$의 시간을 가진다는 것이다.

 

divide and conquer

앞서 말했듯 퀵 정렬 또한 분할 정복 알고리즘의 예시 중 하나이다. 작동 방식은 다음과 같다.

 

1. q라는 pivot을 기준으로 배열을 나눈다. A[p ... q - 1] and A[q + 1 ... r]

2. 각각의 배열은  A[q]를 기준으로 작은 값과 큰 값으로 분류된다.

3. 나눠진 각각의 배열에서 또 pivot을 설정하여 재귀적으로 진행한다.

 

Partition(A, p, r)

 

 

그럼 pivot을 기준으로 나누는 partition 함수는 어떻게 작동할까? quicksort(A, p, r) 함수를 보면 알겠지만 partition 함수는 배열 A를 q를 기준으로 위아래를 나눠주고, q의 최종 인덱스를 반환한다. 그러면 이 최종 인덱스를 기준으로 다시 quicksort를 재귀적으로 호출하는 것이다.

코드만 봐서는 이해가 잘 안가기 때문에 그림과 함께 설명을 해보겠다. 먼저 p와 r은 분류하려고 하는 배열의 처음과 끝 인덱스를 의미한다. 처음 인덱스인 p부터 r - 1까지 탐색을 하면서 우리가 pivot으로 설정한 A[r]보다 작을 때만 +1을 해주며 pivot이 해당 배열에서 현재 몇 번째 위치에 해당되는지를 알 수 있다. 하는 과정에서 우리가 지나는 A[j]는 pivot의 값보다 작기 때문에 i(pivot이 아직까지 들어갈 수 있는 위치)와 교환해 주며 pivot보다 큰 값들을 오른쪽으로 옮겨주는 것이다. partition을 한 번 거치면 pivot을 기준으로 좌/우 에는 pivot보다 작고 pivot보다 큰 값이 위치하게 된다. 이렇듯 partition은 해당 배열을 한번 탐색하기 때문에 $\Theta(n)$의 시간 복잡도를 갖게 된다.

 

Performance of quicksort

 

퀵 정렬은 특이하게도 이미 배열이 어느 정도 정렬이 되어있는지에 따라 성능이 결정된다. 만약 partition 함수의 반환값이 계속해서 한쪽으로 치우쳐 있다면 계속해서 배열 전체를 탐색해야 하므로 $\Theta(n^{2})$의 시간 복잡도를 갖지만, partition의 반환값이 어느 정도 균형이 잡혀 있다면 $\Theta(n · \log{n})$의 시간 복잡도를 갖게 된다.

 

worst case

$$T(n) = T(n - 1) + T(0) + \Theta(n) = T(n - 1) + \Theta(n) = \Theta(n^{2})$$

 

best case

$$T(n) = T(n/2) + \Theta(n) = \Theta(n·\log{n})$$

 

A randomized version of quicksort

 

이런 치우침을 방지하기 위해 배열의 마지막을 pivot으로 설정하는 정통적인 방식이 아니라 난수로 고르는 방법 또한 존재한다. 이럴 때에는 $\Theta(n·\log{n})$이 보장된다.