퀵 정렬(Quick sort)

#들어가기

이번 시간에는 분할정복법을 사용한 퀵 정렬(quick sort)를 알아보겠습니다.

#퀵 정렬(quick sort)

먼저 퀵 정렬(quick sort)의 간략한 개념부터 살펴보겠습니다.

위의 사진에서 볼수 있듯이

• pivot을 선택
• pivot을 기준으로 분할
• 분할된 구역에서 다시 순환적으로 정렬(정복)

즉, 퀵 정렬(quick sort)의 중요한 부분은 ‘어떻게 pivot보다 작은 값과 큰 값을 구분해 정렬하는냐’에 있습니다.

qsort(A[], p, r) {  // p는 배열의 첫번째 index 값, r은 마지막 index 값
    if(p < r) then {
        q = partition(A[], p, r); // 분할
        qsort(A[], p, q-1); // pivot보다 작은 영역 정렬
        qsort(A[], q+1, p); // pivot보다 큰 영역 정렬
    }
}

partition(A[], p, r) {
    partiton이 하는 일은 배열에서 pivot을 기준으로 큰 영역과 작은 영역으로 재배치 한 후,
    바뀐 pivot의 index값을 반환 합니다.
}

pseudo code를 보면 실제로 partition 함수에서 pivot을 기준으로 영역을 나누고 바뀐 pivot의 위치를 반환하면 그 이후는 재귀 함수 호출로 간단히 구현이 가능합니다.
partition 함수를 조금 더 구체화 해보겠습니다.

partition(A[], p, r) {
    x←A[r]; // x, 현재 pivot의 값
    i←p-1;  // i, 작은 영역의 마지막 요소를 가르키는 변수
    
    for j←p to r-1 // 배열을 전체 탐색
        if A[j] ≤ x then // 해당 배열의 값이 pivot보다 작은 경우
            i←i+1;  // i 값 증가
            exchange A[i] and A[j]; // i와 j의 교체 
        
    exchange A[i+1] and A[r]; // pivot 위치 선정, 작은 영역의 마지막 index + 1로 이동
 return i+1;
}

partition의 pseudo code에서 왜 i와 j의 값을 교체하는지 조금은 헷갈릴수 있습니다. 예를 한번 들어보겠습니다.

다음과 같은 상황에서 pivot의 값, x의 값은 15이고 j = 4, i = 0인 상황입니다. A[j]의 경우 pivot보다 작으므로 i값이 1 증가하면 i = 1이 됩니다. A[1]은 현재 pivot보다 큰 영역의 숫자이므로 A[j]와 교환을 해도 그 영역은 유지가 됩니다.

즉, i 보다 작은 index 영역이 pivot보다 작은 영역임을 유지하면 됩니다.

그렇다면 시간 복잡도는 어떻게 될까요? 최악의 경우 n의 제곱이 됩니다. 아이러니하게도 퀵 정렬(quick sort)의 최악의 경우는 이미 정렬된 배열의 가장 큰 값이나 가장 작은 값을 pivot으로 선택할 경우 입니다. 이럴 경우 pivot의 한 쪽은 정렬을 하지 않습니다. pivot 자체가 가장 큰 값이거나 가장 작은 값이기 때문이죠.

자세히 시간 복잡도를 보면

• T(n) = T(0) + T(n-1) + O(n)
• T(n-1) = T(0) + T(n-2) + O(n-1)
• T(n-2) = T(0) + T(n-3) + O(n-2)

pivot을 제외한 왼쪽 영역을 정렬하는데 시간 T(n) = T(n-1) + O(n)이 됩니다. 이런 식으로 T를 계속 치환해 나가다보면 T(n) = O(1) + O(2) + O(3) + … + O(n) 이 됩니다. 이는 {n(n-1)}/2로 다시 쓸수 있으므로 최악의 경우 시간 복잡도는 O(n^2)이 됩니다.

최선의 경우는 정렬되지 않은 상태에서 정확히 pivot이 중간 값일 떄 입니다. 시간 복잡도는 T(n) = nlogn이 됩니다. 이는 n이 pivot을 중심으로 정확히 절반 씩 영역을 나누는데 O(n)입니다. 또 절반씩 나누어진 영역에서 pivot을 중심으로 반을 나누면 O(n/2)이고 두 영역이니 이 역시 O(n)입니다.

결국은 최선의 경우 시간 복잡도는 n * 분할된 횟수인 logn이 됩니다.

그렇다면 우리는 최악의 경우 O(n^2)이 나올수도 있는 퀵 정렬(quick sort)를 쓰는 이유는 무엇일까요?

답은 퀵 정렬(quick sort)은 극단적인 최악의 경우를 제외하면 모든 정렬에서 평균 O(nlogn)이 나오기 떄문입니다.

1:9로 나누는 pivot이 선택된다고 가정했을때 시간 복잡도가 O(nlogn)이 나오는 걸 확인할수 있습니다.

#마치며

이로써 퀵 정렬(quick sort)의 정리를 마치겠습니다.
설명 도중 틀린 설명이 있다면 코멘트로 남겨주세요. 수정하겠습니다!!

#참조

부경대학교 권오흠 교수님 강의 | 2015년 1학기