퀵 정렬 (Quick Sort)

퀵 정렬은 토니 호어 (Tony Hoare) 가 1959년에 고안한 알고리즘으로 피벗 (pivot) 을 기준으로 좌우를 나누는 특징으로 인해 파티션 교환 정렬 (Partition-Exchange Sort)라고도 불립니다. 퀵정렬은 피벗을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 계속 나누어 분할해가며 정렬하는데요, 빠르고 효율적으로 최선의 경우 $O(n\log n)$의 시간 복잡도를 가집니다. 

그렇다면 맨 처음 단계에서 피벗을 어떻게 설정해야 할까요? 여러 인덱스가 피벗이 될 수 있지만 일반적으로 맨 왼쪽 혹은 맨 오른쪽 인덱스를 피벗으로 설정하게 됩니다. 배열 [2,8,7,1,3,5,6,4]에 대해 왼쪽, 오른쪽 피벗을 살펴보도록 하죠.

 

왼쪽 피벗

왼쪽 피벗의 경우 left 포인트, right 포인트의 투 포인터가 각각 배열의 왼쪽 끝, 오른쪽 끝에서부터 서로 근접하는 방향으로 이동하면서 left 포인트가 피벗보다 큰 값, right 포인트가 피벗보다 작은 값일 때 이 둘을 swap하게 됩니다. 

 

< STEP 1 >

첫 번째 스텝입니다. Left 포인트는 왼쪽에서부터 right 포인트는 오른쪽에서부터 움직이면서 left 포인트는 피벗보다 값이 큰 8 (두 번째 인덱스), right 포인트는 피벗보다 값이 작은 1 (네 번째 인덱스) 에서 멈추게 됩니다. 이 때, 8과 1을 swap합니다.

 

< STEP 2 >

두 번째 스텝에서도 left 포인트, right 포인트를 해당 방향으로 진행시킵니다. 이번에는 left 포인트가 7 (세 번째 index), right 포인트는 1 (두 번째 index)에서 멈췄네요. 이번에도 swap을 진행하지만 left 포인트와 right 포인트의 위치가 교차되었으므로 피벗과 작은 값 (1)의 위치를 바꿉니다.

 

< STEP 3 >

결과적으로 기존 피벗이었던 2를 기준으로 왼쪽은 2보다 작은 값인 1, 오른쪽에는 2보다 큰 값들이 모여 있습니다. 피벗을 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값을 잘 partition 했습니다. 이후 과정은 step 1-3을 피벗 오른쪽 배열, 피벗 왼쪽 배열에 각각 재귀적으로 적용해주면 됩니다. 코드를 한 번 살펴볼까요?

 

파이썬 코드

def quick_sort(array, start, end): # array 입력과 함께 파티션을 나눌 배열 대상
    ## 재귀구문의 종료 조건, 원소가 1개일 때 종료
    if start >= end:
        return 
        
    pivot = start # 피벗을 첫 번째 원소
    left_point = start + 1 # left 포인트는 시작점 다음
    right_point = end
    
    while left_point <= right_point:
        ## 피벗보다 큰 원소 찾기 (left point)
        while left_point <= end and array[left_point] <= array[pivot]:
            left_point += 1
        ## 피벗보다 작은 원소 찾기 (right point)
        while right_point >= start and array[right_point] >= array[pivot]:
            right_point += 1
           
        ## left 포인터와 right 포인터가 교차하면 피벗과 right 포인터 swap
        if left_point > right_point:
            array[right_point], array[pivot] = array[pivot], array[right_point]
        ## 교차하지 않았다면 left 포인터 right 포인터 swap
        else:
            array[left_point], array[right_point] = array[right_point], array[left_point]
            
    ## 나눠진 파티션에 대해 재귀적으로 quick_sort 수행
    quick_sort(array, start=start, end=right_point-1)
    quick_sort(array, start=right_point+1, end=end)
    
quick_sort(array, start=0, end=len(array)-1)
        

 

오른쪽 피벗

오른쪽 피벗도 왼쪽 피벗처럼 같은 방법으로 풀 수 있습니다. left 포인터와 right 포인터를 양 끝에 두고 right 포인터는 피벗보다 큰 값, left 포인터는 피벗보다 작은 값을 찾는 방향으로 풀면 됩니다. 요지는 분할의 결과 피벗의 왼쪽은 작은 값들, 오른쪽은 큰 값들이 놓여지게 하면 됩니다. 오른쪽 피벗은 살짝 다른 방향으로 풀이해 볼까요?

 

< STEP 1 >

이번에는 left 포인트, right 포인트 모두 배열 첫 번째 인덱스부터 시작합니다. right 포인터를 움직이면서 피벗보다 작은 값이 있을 경우 left 포인터와 right 포인터의 값을 swap하고 left 포인터의 값을 1 증가시킵니다. 이 경우는 left, right 포인터가 같은 값을 가지니 변함이 없겠네요.

 

< STEP 2 >

Right 포인터를 계속 진행시키면서 피벗보다 작은 값은 네 번째 인덱스에 위치한 1입니다. left 포인터는 아까 step 1에서 증가했으므로 두 번째 인덱스에 있었던 8과 네 번째 인덱스의 1이 swap 되겠네요.

 

< STEP 3 >

Step 2와 마찬가지입니다. 다섯 번째 인덱스에 있었던 3에서 right 포인트는 멈추고 left 포인터의 7과 swap합니다.

 

< STEP 4 >

Right 포인터가 다 진행이 되었으면 left 포인터와 피벗을 스왑합니다. 결과적으로 피벗 4를 기준으로 왼쪽에는 4보다 작은 값들, 오른쪽에는 4보다 큰 값들이 위치하게 되었네요. 코드를 한 번 보겠습니다.

 

파이썬 코드

def quick_sort(array, start, end):
    if start >= end:
        return

    def partition(s, e): # start / end
        pivot_value = array[e]
        left_point = s
        for right_point in range(s, e):
            if array[right_point] < pivot_value:
                array[right_point], array[left_point] = array[left_point], array[right_point]
                left_point += 1
        a[left_point], a[right_point] = a[right_point], a[left_point]
        
        return left_point
        
    pivot = partition(start, end)
    quick_sort(array, start=start, end=pivot-1)
    quick_sort(array, start=pivot+1, end=end)
    
quick_sort(array, 0, len(array)-1)

 

시간 복잡도

아까 잠깐 언급했듯이 퀵 정렬의 시간 복잡도는 최선의 경우 $O(n\log n)$입니다. 그렇다면 최선의 경우는 언제일까요? 이상적인 경우 분할이 절반씩 일어난다면 $O(n\log n)$이 될 겁니다. 매번 n번의 연산을 수행하면서 분할이 $\log n$만큼 될것이기 때문이죠. 반면, 최악의 경우 이미 정렬되어 있는 배열에 대해 퀵정렬을 수행한다면 어떻게 될까요? 이미 정렬되어 있기 때문에 피벗이 움직이지 않게 될 것이고 n번에 걸쳐 전체를 비교하게 될 겁니다. 이런 경우라면 $O(n^2)$의 시간 복잡도가 소요되겠죠.

 

홍머스 정리

• 피벗 기준으로 왼쪽은 작게, 오른쪽은 크게
• 나눈 후에 재귀적으로 반복

참조

• www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=23
• <파이썬 알고리즘 인터뷰>, p485-487