[edu] 퀵 소트

퀵 정렬(Quick Sort)

28 Sep 2017 | algorithm

이번 글에서는 퀵 정렬(Quick Sort) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드 구현은 이곳을 참고하였습니다. 그럼 시작하겠습니다.

개념

퀵 정렬은 분할정복(divide and conquer) 방식으로 작동합니다. 그 절차는 다음과 같습니다.

• 리스트 가운데서 하나의 원소를 고릅니다. 이를 피벗(pivot)이라 합니다.
• 피벗 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오도록 하여 리스트를 둘로 분할합니다.
• 분할된 두 개 리스트 각각에 재귀적으로 이 과정을 반복합니다.

예시

다음과 같은 리스트를 정렬해보겠습니다.

[5, 3, 7, 6, 2, 1, 4]

첫번째 값(5)을 피벗으로 택해보겠습니다. (마지막 요소 4를 택해도 관계 없습니다) 이 값보다 작은 값들로만 구성된 리스트와 큰 값들로만 구성된 리스트 둘로 분할합니다. 이를 각각 LESSOR와 GREATER라고 명명해보겠습니다.

LESSOR = [3, 2, 1, 4]

GREATER = [7, 6]

그리고 나서 LESSOR와 GREATER 각각에 같은 작업을 해당 리스트의 요소 개수가 하나가 될 때까지 재귀적으로 반복합니다.

구현

퀵 정렬을 파이썬으로 구현한 코드는 다음과 같습니다.

def quick_sort(arr):
    size = len(arr)
    if size <= 1:
        return arr
    else:
        pivot = arr[0]
        greater = [element for element in arr[1:] if element > pivot]
        lesser = [element for element in arr[1:] if element <= pivot]
        return quick_sort(lesser) + [pivot] + quick_sort(greater)

계산복잡성

퀵 정렬의 계산복잡성은 피벗을 어떻게 선택하느냐에 따라 달라집니다. 최악의 경우는 다음과 같습니다. 다시 말해 피벗의 왼쪽(LESSOR) 요소가 매번 하나인 경우입니다. 이렇게 되면 높이가 n$n$, 각 층에서 n$n$개의 요소에 대해 정렬을 수행해야 하므로 O(n2)$O(n^2)$의 계산복잡도를 가지게 됩니다.

가장 좋은 경우는 다음과 같습니다. 분할 과정이 다음과 같이 균형적이어서, 계산 트리의 높이가 n$n$에서 log2n${\log }_{2}n$으로 줄어들게 되기 때문입니다. 이렇게 되면 높이가 log2n${\log }_{2}n$, 각 층에서 n$n$개의 요소에 대해 정렬을 수행해야 하므로 O(nlog2n)$O(n{\log }_{2}n)$의 계산복잡도를 가지게 됩니다.

Average case의 경우에도 퀵 정렬은 O(nlogn)$O(n\log n)$의 계산복잡도를 가진다고 합니다. 아울러 피벗을 선택할 때 정해진 위치가 아니라 랜덤하게 선택하거나, 몇 개 값을 랜덤 샘플링해 이 값들의 중앙값(median)에 가까운 값을 피벗으로 정하면 계산복잡도를 다소 낮추는 데 도움이 된다고 합니다.

퀵 정렬의 특징

설명의 편의를 위해 피봇을 기준으로 작은 값을 왼쪽, 나머지를 오른쪽으로 보내는 과정을 재귀적으로 반복한다고 했습니다만, original code는 이보다는 살짝 더 복잡합니다. 정렬 수행 과정에서 별도 저장 공간을 필요로 하지 않는 in-place sort를 지향하고자 하기 때문인데요. original code의 수행 과정을 보시려면 이곳을 참고하시면 좋을 것 같습니다. 수행과정을 도식화하면 다음 그림과 같습니다. 이 과정에서 같은 값의 상대적 위치가 바뀔 수 있습니다(unstable sort).