퀵 정렬 알고리즘

31 Dec 2021

Reading time ~3 minutes

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 퀵 정렬은 기준 데이터를 설정하고 그 기분보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘이다.

기준 설정 -> 큰 수와 작은 수를 교환 -> 리스트를 반으로 나누기

퀵 정렬에서는 피벗^Pivot이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ‘기준’을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)이 있다. 호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다.

리스트에서 첫 번째 데이터를 피벗으로 정한다.
왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
큰 데이터와 작은 데이터의 위치를 서로 교환해준다.

이러한 과정을 반복하면 ‘피벗’에 대하여 정렬이 수행된다. 양쪽에서 데이터 두개씩 선택해서 왼쪽 데이터가 오른쪽보다 크면 서로 바꿔주면 된다. 단, 양쪽에서부터 가운데로 접근하다보면 엇갈릴 때가 있는데, 이럴 경우 ‘피벗’과 작은 데이터의 순서를 서로 변경한다.

피벗 왼쪽 데이터들은 피벗보다 작은 데이터들, 오른쪽 데이터들은 피벗보다 큰 데이터들이 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시킨다. 왼쪽 리스트와 오른쪽 리스트에서도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

[퀵 정렬을 코드로 직접 구현]

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        return
    pivot = start     # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:  # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:  # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬의 시간 복잡도

선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N²)을 보장한다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다.

일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다. 즉, log₂N을 의미하며 데이터의 개수 N이 1,000일 때 log₂N은 10가량이다. N = 1,000일 때 log₂N ≒ 10은 매우 작은 수임을 이해할 수 있다.

데이터의 개수가 많을수록 차이는 매우 선명하게 드러난다. 표는 ‘평균 시간 복잡도’를 기준으로 비교한 것이다. |데이터의 개수(N)|N²(선택 정렬, 삽입 정렬)|Nlog₂N(퀵 정렬)| |—————|——————–|————-| |N=1,000 |≒ 1,000,000 |≒ 10,000 | |N=1,000,000 |≒ 1,000,000,000,000|≒ 20,000,000|

다만, 퀵 정렬의 시간 복잡도도 마찬가지로 최악의 경우 O(N²)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 피벗을 가장 왼쪽 데이터로 삼을 때, ‘이미 데이터가 정렬되어 있는 경우’에는 매우 느리게 동작한다. 삽입 정렬과 반대다. 파이썬이나 C++에서 제공하는 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장해주기 때문에 걱정하지 않아도 된다.

ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의

SW ALGORITHM