[정렬] 퀵 정렬 :: 늦깎이 IT

[퀵 정렬]

퀵 정렬은 앞서 알아봤던 합병 정렬과 마찬가지로 '분할 정복'에 근거하여 만들어진 정렬 방법이다.

실제로 퀵 정렬 역시 정렬대상을 줄여나가는 과정을 포함한다. 그러나, 정렬 대상을 반씩 분할했던 합병정렬과는 달리 퀵 정렬은 데이터를 반드시 균등한 크기로 분할하지 않는다. 

우선, 퀵 정렬은 '피벗(Pivot)'이라고 불리는 기준점으로 정렬을 수행한다. 정렬해야 하는 데이터들 중, 임의의 데이터를 '피벗'으로 지정한 후, 다른 데이터들과의 비교를 통해 [피벗보다 작은 데이터] / [피벗보다 큰 데이터]로 나눈다.

퀵 정렬이 균등한 크기로 분할하지 않는 이유도 여기에 있다. '피벗'보다 [작은 값]의 갯수와 [큰 값]의 갯수가 균일하지 않을 수 있기 때문이다.

[그림]에서는 마지막 값을 피벗으로, 아래 설명에서는 첫 번째 값을 피벗으로 한다.

[의사 코드]

Quick-sort(A[], P,R)
    if(P < R) then {
        Q = partition(A[], P, R)
        Quick-sort(A[], P, Q-1)
        Quick-sort(A[], Q+1, R)
    }
 
Partition(A[], P, R)
    A[P...R]의 데이터들을 A[i]을 기준으로 재배치하고
    i를 리턴한다.

1)번 라인의 Quick-sort 함수는 A[P...R]을 정렬하는 함수이다.

8)번 라인의 Partition 함수는 A[P...R]을 '피벗' A[i]를 기준으로 [작은 값] / [큰 값]으로 나눈 후, '피벗'의 인덱스를

반환하는 함수이다. 이때 반환되는 인덱스 i의 값 A[i]는 A[P...R]에서 이미 정렬이 완료된 값이다.

퀵 정렬의 핵심인 Partition 함수의 원리에 대해서 살펴본다.

1. 

1) '피벗' 값은 임의로 정할 수 있지만, 여기서는 맨 왼쪽 값을 '피벗' 값으로 선택한다.

2) left는 배열의 맨 왼쪽 값, right는 배열의 맨 마지막 값이다.

3) low는 pivot보다 한 칸 오른쪽에 있는 값, high는 맨 왼쪽에 있는 값이다.

2.

1) low 값은 '피벗' 값보다 [큰 값]을 찾을때 까지 오른쪽으로 이동한다.

2) high 값은 '피벗' 값보다 [작은 값]을 찾을때 까지 왼쪽으로 이동한다.

3) low값과 high값이 고정되어있다면, low와 high가 가리키는 데이터들을 서로 교환한다.

4) 따라서, 7과 4의 값이 바뀐 것을 확인할 수 있다.

3. 

1) low 값은 '피벗' 값보다 [큰 값]을 찾을때 까지 오른쪽으로 이동한다.

2) high 값은 '피벗' 값보다 [작은 값]을 찾을때 까지 왼쪽으로 이동한다.

3) low값과 high값이 고정되어있다면, low와 high가 가리키는 데이터들을 서로 교환한다.

4) 따라서, 9와 2의 값이 바뀐 것을 확인할 수 있다.

4.

1) 만약에, low와 high가 가리키는 위치가 역전되었다면(low > high) 더 이상 탐색을 멈춘다.

2) 이 의미는, 이 배열에서 '피벗' 값을 기준으로 [작은 값] / [큰 값]으로 나눌 데이터가 없다는 뜻이다.

3) low와 high가 역전되었다면, pivot의 값과 high가 가리키는 값을 교환한다.

4) 이때 피벗 값인 5와 high가 가리키는 값인 2를 자세히 살펴보면, high는 피벗 값보다 [작은 값] 중에서 가장 뒤에 있는 값을 가리키는 것을 알 수 있다.

5) 그렇기 때문에, '피벗' 값과 피벗 값보다 [작은 값]들 중 맨 뒤에 있는 값을 바꿔주게 되면, 피벗 값을 기준으로 [작은 값] / [큰 값]으로 배열을 정렬할 수 있다.

5.

1) 모든 연산이 끝나고나면, 초기 '피벗' 값이였던 5가 제 위치를 찾은 것을 확인할 수 있다.

[JAVA 코드]

public static void quickSort(int[] arr, int left, int right) {
 
        if (left <= right) {
 
            int pivot = partition(arr, left, right);
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
 
    }
 
    public static int partition(int[] arr, int left, int right) {
 
        int pivot = left;
        int low = pivot + 1;
        int high = right;
 
        while (low <= high) {
 
            while (arr[pivot] >= arr[low] && low <= right)
                low += 1;
 
            while (arr[pivot] <= arr[high] && high >= (left + 1))
                high -= 1;
 
            if (low <= high)
                swap(arr, low, high);
        }
        swap(arr, pivot, high);
        return high;
    }

[시간 복잡도]

합병 정렬에서의 시간 복잡도는 T(n) = T(n/2) + T(n/2) + n 이었다. 그러나 위에 설명했듯이, 퀵 정렬은 피벗을 기준으로 나뉘어지는 데이터의 수가 균일하지 않으므로 합병 정렬의 시간복잡도와 다르다.

1. 최악의 경우

퀵 정렬의 최악의 시간 복잡도는 피벗을 기준으로 항상 한 쪽은 0개, 다른 쪽은 N-1개로 분할되는 경우이다.

이런 경우는, 이미 데이터가 정렬되어있는 경우 발생한다.

퀵 정렬의 최악의 경우에는 아래와 같이 시간 복잡도를 계산할 수 있다. 

T(N) = T(0) + T(N-1) + O(N-1) = T(N-2) + O(N-2) + O(N-1) = .... = O(N^2)

1) 피벗을 기준으로 데이터를 분할할 때 걸리는 시간은 N-1이다. N개의 원소에서 1개를 피벗 값으로 지정하고 나머지 N-1개의 데이터와 피벗 데이터를 비교함으로써 데이터를 분할한다. 즉, 데이터를 분할하는데 걸리는 시간은 피벗을 기준으로 분할된 데이터가 균일한지 아닌지와는 상관이 없다는 뜻이다.

2) N개의 데이터를 퀵 정렬하는데 걸리는 시간 복잡도를 T(N)이라고 한다면, 최악의 경우에는 항상 한 쪽은 0개, 다른 쪽은 N-1개로 분할되기 때문에 T(N) = T(0) + T(N-1)이라고 표현할 수 있다.

3) T(N-1)은 다시 T(0) + T(N-2) + O(N-2)로 표현할 수 있다. 재귀적으로 이 함수를 풀어나가다보면 아래 그림과 같은 식을 얻을 수 있다.

2. 최선의 경우

퀵 정렬의 최적의 시간 복잡도는 피벗을 기준으로 분할되는 데이터의 수가 균일한 경우이다. 합병 정렬에서 N개의 데이터를 정렬하기 위해 N/2씩 분할하여 정렬했던 것과 똑같은 시간복잡도를 갖게 된다.

T(N) = T(N/2) + T(N/2) + O(N) = .... = O(NlogN)

3. 더 생각해보기

 피봇을 기준으로 최악의 경우, 최선의 경우를 살펴보았다. 그러나, 데이터가 완전히 한쪽으로 치우치거나, 정확히 절반씩 나뉘어지는 경우는 극히 드물다고 생각된다. 그럼 평균적으로 퀵 정렬의 시간복잡도는 얼마나 될까?

피벗을 기준으로 분할되는 데이터의 비율이 1 : 9 라고 가정해보자.

위 그림을 살펴보자.

1) 처음 N개의 데이터를 정렬하기 위해 피벗을 기준으로 분할한다.

2) 이 그림을 살펴보면, 왼쪽 방향으로 뻗어나가는 (비율 1에 해당되는) 부분의 깊이가 오른쪽보다 항상 얕다는 것을 알 수 있다.

3) 그리고 각각의 깊이에 대해서 피벗을 기준으로 분할하기 위해 걸리는 시간 복잡도는 N이다. 위에서 설명했듯이 N개의 데이터를 분할하는데 걸리는 시간은 O(N)이기 때문이다.

4) 그렇다면 각각의 깊이(레벨)에 O(N)만큼의 시간이 걸린다면, 전체 시간 복잡도를 구하기 위해서는 이 트리의 전체 높이를 알면 된다. 즉, 가장 오른쪽 방향의 깊이가 몇인지 계산하면 된다.

5) 오른쪽 방향으로 뻗어나갈 때마다 N → (9N/10) → (81N/100) → (273N/1000) 식으로 증가한다. 수식으로 표현하면 아래와 같고, 이를 만족하는 K를 구하면 아래와 같다.

 

즉, 이 식으로부터 T(N) = O(NlogN) 만큼의 시간이 걸린다는 것을 계산할 수 있다. 퀵 소트의 성능에 크게 영향을 미치는 것은 데이터를 얼마나 균등하게 분할하느냐에 따라 성능이 좌지우지 된다는 것을 알 수 있고, 아주 극단적인 경우만 아니라면 위와 같이 우수한 성능을 낼 수 있다는 것을 알 수 있다.

4. 피벗의 선택

1) 첫 번째 값이나 마지막 값을 피벗으로 선택하기

위의 소스코드로 구현한 퀵 정렬은 첫 번째 값을 '피벗'으로 선택했지만 이는 좋은 방법이 아닐 수 있다.

그 이유는 우리가 어떤 데이터를 정렬할 때 그 데이터가 정렬되지 않은 랜덤한 데이터일 가능성이 낮다고 볼 수 없다.

예를 들어, 우리가 이전 포스팅에서 [게시판 만들기]를 진행했을 때, 게시글 목록을 DB에서 SELECT하면서 order by 구문을 이용해서 정렬을 수행했다.

또한, 시스템 A와 B가 있다고 가정해보자. 이때 시스템 A가 입력으로 받는 데이터는 B시스템 혹은 그 외의 다른 시스템들의 아웃풋이 될 수 있다. 물론 B시스템의 아웃풋이 정렬되지 않은 랜덤 데이터라면 상관없겠지만 시스템을 개발하는 과정에서 그럴 가능성은 낮다고 볼 수 있다.

따라서, 정렬 대상의 데이터의 첫 번째 혹은 마지막 값을 "피벗"으로 선택하는 것은 좋은 방법이라고 할 수 없다.

2) 중간 값 선택하기

첫 번째 값과 마지막 값, 그리고 가운데 값 중에서 우선순위가 중간인 값을 "피벗"으로 선택하는 것이다.

이 방법으로 "피벗"을 선택하게 되면 "피벗"값이 우선순위가 가장 낮거나, 높은 경우일 가능성은 낮출 수 있을 것이다.

3) 랜덤으로 선택하기

"피벗"을 선택할 때, 어떠한 규칙을 가지고 선택하는 것이 아니라 "피벗"의 값 자체를 랜덤하게 고르는 것이다.

이렇게 되면, 어떠한 입력이 최악의 경우인지 예측하기 매우 힘들다. 따라서, 어느 입력이 최악의 경우라고 할 수 없지만, 최악의 실행시간을 갖게되는 입력은 존재할 수 있다.