퀵 정렬(Quick Sort) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

퀵 정렬(Quick Sort)?

병합정렬과 마찬가지로 분할 정복 알고리즘을 사용한 정렬 방법이다. 주어진 배열 중 하나를 선택해 기준으로 세운 뒤 해당 원소를 기점으로 작거나 큰 원소를 서로 분리하여 다시 재귀호출하는 방식이다.

퀵 정렬 동작

퀵 정렬은 다음의 과정으로 진행된다.

1. 배열 중 하나의 원소를 고른다. 보통 좌측이나 우측 혹은 중간 지점을 선택하며 기준으로 세워진 원소를 피벗(pivot)이라 한다.
2. 오름차순이라면 피벗 좌측에는 피벗보다 작은 값, 우측에는 피벗보다 큰 값이 오게끔 재배열한다.
3. 피벗을 제외하고 분할된 두 리스트를 다시 재귀호출하여 재배열한다.

위 과정에 따래 정렬된 배열을 다음의 과정으로 이루어진다.

• 분할(Divide) : 입력 배열을 피벗을 기준으로 대소 관계에 따라 좌, 우측으로 분할한다.
• 정복(Conquer) : 점차적으로 부분 배열을 정렬해나간다.
• 결합(Combine) : 완성된 배열을 리턴한다.

결국 피벗을 기준으로 분할하기 때문에 피벗의 값이 배열에서 어떤 의미를 갖느냐에 따라 시간복잡도의 차이가 발생한다. 새로운 임시 배열을 선언하여 공간복잡도를 희생하는 방법도 있고 효율성을 위해 n에 걸쳐 배열의 중간값을 찾고 정확히 2등분된 부분 배열을 얻는 방법도 있다.

pivot을 기준으로 원소들을 이리저리 swap하다보니 원소간 다른 속성에 대한 순서가 이리저리 바뀌는 불안정 정렬에 해당한다.(Unstable Sort) 그러나 Stable하고 Not In-Place 정렬인 병합 정렬과는 정확히 반대로 Unstable하고 In-Place 정렬이므로 상황에 따라 골라서 선택하면 되겠다. 참고로 python의 내장함수 sort는 Stable한 정렬 함수이다.

최선의 경우 분할 정복처럼 깔끔하게 $O(nlog\ n)$일 수도 있고 최악의 경우 pivot이 항상 정렬순서의 끝분이어서 1개씩밖에 분할되지 않아 결국 $O(n^2)$일 수도 있다. 그렇다면 병합정렬에 비해 전혀 나을게 없어 보일 수도 있지만 메모리 요구량이 병합정렬은 $O(n)$인 반면 퀵 정렬은 $O(log\ n)$으로 두 가지 방법을 상황에 따라 사용하면 되겠다. 물론 별도로 정렬 알고리즘을 설계하라고 주문받지 않았다면 코딩테스트나 실무에서는 고도로 효율성을 따져가며 설계된 내장함수를 사용하는 게 맞겠다. 여기서는 항상 pivot이 배열의 우측 원소를 기준으로 한다고 가정하자. 이 방법을 로무토 파티션 계획이라 부르기도 한다.

위 배열을 정렬한다고 할 때 전체 정렬 과정은 다음과 같다.

정렬 과정을 살펴보면 pivot이 정확히 중앙에 위치하여 이등분된다면 merge sort와 별 다를 바가 없어 시간복잡도는 $O(nlog\ n)$이 된다. 그러나 모든 정렬 과정에서 pivot이 항상 끝자리에 위치한다면 분할 과정을 거쳐도 부분 배열의 길이가 1씩 밖에 줄어들지 않아 시간 복잡도는 $O(n^2)$이 된다. 이는 최선이든 최악이든 변함없이 $O(nlog\ n)$을 보여주었던 병합 정렬과 다른 면을 보인다. 그리고 정렬 과정에 swap이 포함되므로 정렬하고자 하는 속성 외에 다른 속성과의 관계를 보장하지 않아 불안정 정렬(UnStable)하다. 공간복잡도 즉, 메모리는 스택에 분할된 부분 배열이 포함되므로 최악의 경우라면 약 $O(n)$을 요구하겠지만 일반적인 경우 $O(log\ n)$을 요구한다.

python 코드

def quick(arr, lo, hi):
    def partition():
        pivot = arr[hi]
        left = lo
        for right in range(lo, hi):
            if arr[right] < pivot:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
        arr[left], arr[hi] = arr[hi], arr[left]
        return left

    if lo < hi:
        pivot = partition()
        quick(arr, lo, pivot - 1)
        quick(arr, pivot + 1, hi)
    return arr
a = [3, 1, 2, 5, 4, 6]
b = [6, 5, 4, 3, 2, 1]
c = [5, 5, 3, 3, 1, 1]
r_a, r_b, r_c = len(a) - 1, len(b) - 1, len(c) - 1
print(f'quick a:{quick(a, 0, r_a)}, b:{quick(b, 0, r_b)}, c:{quick(c, 0, r_c)}')