퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 기준값 하나를 고른 뒤 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 몰아놓고, 양쪽을 재귀적으로 같은 방식으로 정렬하는 알고리즘이다. 이 기준값을 피벗(pivot)이라고 부른다.

평균 O(n log n)에 상수가 작아 실제로 가장 빠른 정렬 중 하나이지만, 피벗을 잘못 고르면 O(n²)까지 떨어진다. 이 "빠르지만 최악이 나쁘다"는 성질과 그 이유를 설명할 수 있는지가 면접에서 묻는 핵심이다.

개념과 원리

퀵 정렬의 한 단계는 파티션(partition)이라고 부른다. 피벗을 하나 정하고 배열을 훑어서, 피벗보다 작은 값들과 큰 값들을 갈라놓는 작업이다. 파티션이 끝나면 피벗은 최종 위치에 확정된다. 이 자리는 다시는 바뀌지 않는다.

이렇게 피벗 하나를 제자리에 놓고 나면, 왼쪽 그룹과 오른쪽 그룹을 각각 같은 방법으로 정렬하면 된다. 그룹의 크기가 1 이하가 되면 멈춘다.

파티션 과정 (Lomuto 방식)

구현이 가장 간단한 방식은 맨 뒤 원소를 피벗으로 삼고, 왼쪽부터 훑으며 피벗보다 작은 값을 앞쪽으로 모으는 것이다. 변수 i는 "지금까지 모은 작은 값 구역의 끝"을 가리킨다.

시간 복잡도

구분	복잡도	언제 생기는가
최선 / 평균	O(n log n)	피벗이 배열을 대체로 반반씩 가를 때
최악	O(n²)	피벗이 매번 최솟값이나 최댓값일 때
공간	O(log n)	재귀 호출 스택. 최악에는 O(n)
안정성	불안정 정렬	멀리 있는 원소끼리 교환하므로

최악의 경우가 언제인지가 중요하다. 맨 뒤를 피벗으로 삼는 구현에 이미 정렬된 배열을 넣으면, 매번 피벗이 최댓값이라 한쪽 그룹이 텅 비고 다른 쪽이 n−1개가 된다. 분할이 반으로 줄지 않으니 깊이가 n이 되어 O(n²)이다. "정렬된 입력이 최악"이라는 이 역설이 면접 단골 질문이다.

구현 코드 예시

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low >= high:                      # 원소가 1개 이하면 정렬 끝
        return arr

    p = partition(arr, low, high)
    quick_sort(arr, low, p - 1)          # 피벗 왼쪽
    quick_sort(arr, p + 1, high)         # 피벗 오른쪽
    return arr


def partition(arr, low, high):
    pivot = arr[high]                    # 맨 뒤를 피벗으로
    i = low - 1                          # 작은 값 구역의 끝

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]   # 피벗을 제자리로
    return i + 1

파이썬으로 짤 때 흔히 보이는, 리스트 컴프리헨션으로 세 조각을 만드는 방식도 있다. 읽기는 훨씬 쉽지만 매 단계 새 리스트를 만들어 O(n) 공간을 더 쓴다.

def quick_sort_simple(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]   # 중복 값을 따로 모아야 무한 재귀를 막는다
    right = [x for x in arr if x > pivot]
    return quick_sort_simple(left) + mid + quick_sort_simple(right)

def quick_select(arr, k):
    """k번째로 작은 원소를 반환한다 (k는 1부터 시작)."""
    low, high = 0, len(arr) - 1
    target = k - 1                       # 0-based 인덱스로 변환

    while low <= high:
        p = partition(arr, low, high)    # 위에서 만든 파티션 함수를 그대로 쓴다

        if p == target:
            return arr[p]                # 피벗이 정확히 그 자리 → 답
        if p < target:
            low = p + 1                  # 오른쪽만 본다
        else:
            high = p - 1                 # 왼쪽만 본다

    return None