퀵 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

1. 피벗 요소를 고릅니다. 예를 들어 마지막 요소나 무작위 요소입니다.
2. 분할(Partition): 피벗보다 작은 요소는 모두 왼쪽으로, 큰 요소는 모두 오른쪽으로 옮깁니다. 이제 피벗은 정렬된 최종 위치에 있습니다.
3. 피벗의 왼쪽 부분과 오른쪽 부분을 각각 재귀적으로 정렬합니다. 이후에 합칠 것은 없습니다.

병합 정렬은 나누기는 쉽고 합치기가 어렵습니다. 퀵 정렬은 반대로 분할에서 일을 다 하고, 같은 배열 안에서 이미 올바른 위치에 있으므로 두 절반을 합치는 비용이 없습니다.

예제: Lomuto 분할 한 번

[10, 80, 30, 90, 40, 50, 70]을 마지막 요소 70을 피벗으로 분할해 봅시다. 인덱스 i는 피벗보다 작은 요소 영역의 끝을 나타내고, j는 왼쪽에서 오른쪽으로 훑습니다.

70은 이제 인덱스 4, 즉 최종 위치에 있습니다. 이어서 퀵 정렬은 [10, 30, 40, 50]과 [90, 80]을 따로 정렬합니다.

파이썬 구현

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

작은 쪽으로 재귀하고 큰 쪽은 반복문으로 처리하면 최악의 경우에도 스택 깊이가 O(log n)으로 유지됩니다. 원리를 설명할 때는 짧은 비(非)제자리 버전이 인기 있지만, 레벨마다 새 리스트를 할당합니다.

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

시간 복잡도와 공간 복잡도

고전적인 최악의 경우는 이미 정렬되었거나 역순인 입력에 첫 번째 또는 마지막 요소를 피벗으로 고정해 쓰는 것입니다. 분할할 때마다 피벗 하나만 빠지므로 O(n) 작업이 n레벨 쌓입니다. 무작위 피벗을 쓰면 어떤 입력에서도 이런 일이 일어날 가능성은 극히 낮습니다.

퀵 정렬과 다른 정렬 비교

퀵 정렬은 안정 정렬이 아닙니다. 분할 중의 교환이 같은 값의 요소를 지나쳐 버릴 수 있기 때문입니다. 메모리 안의 배열에서는 보통 병합 정렬과 힙 정렬보다 빠릅니다. 안쪽 반복문이 단순하고, 제자리에서 동작하며, 메모리를 대체로 순차적으로 접근하기 때문입니다. 많은 C++ 표준 라이브러리 std::sort 구현이 쓰는 introsort는 퀵 정렬로 시작해 재귀가 너무 깊어지면 힙 정렬로 전환하며, 이로써 O(n log n)이 보장됩니다.

피벗 선택, 변형, 흔한 실수

• 피벗 선택: 첫 번째 또는 마지막 요소(간단하지만 정렬된 입력에서 O(n²)), 무작위 요소, 세 값(처음, 가운데, 끝)의 중앙값.
• Hoare 분할: 두 인덱스가 서로를 향해 움직이며 잘못된 쪽에 있는 쌍을 교환합니다. 평균적으로 Lomuto보다 교환이 적습니다.
• 3-way 분할(네덜란드 국기 문제): 작은 쪽, 같은 쪽, 큰 쪽으로 나눕니다. 중복 키가 많은 배열도 빠르게 처리합니다. 일반 Lomuto는 모든 키가 같으면 O(n²)로 떨어집니다.
• 듀얼 피벗 퀵 정렬은 피벗 두 개와 세 부분을 사용하며, Java가 기본 자료형 배열을 정렬할 때 씁니다.
• 퀵셀렉트(Quickselect)는 분할을 한 번 하고 한쪽만 재귀하여 k번째로 작은 요소를 평균 O(n) 시간에 찾습니다.

퀵 정렬을 쓰는 경우

안정성이 필요 없는 메모리 내 배열 정렬에서 퀵 정렬은 좋은 기본 선택입니다. 파이썬에서는 대신 sorted()나 list.sort()를 쓰세요. 이들은 부분적으로 정렬된 데이터에서 빠르고 안정적인 Timsort를 사용합니다. 퀵 정렬 구현은 매우 흔한 면접 과제이며, 최악의 경우, 피벗 선택, 안정성, 또는 퀵셀렉트로 k번째로 큰 요소 찾기에 대한 질문이 이어지는 경우가 많습니다.