퀵 정렬·피벗·세 갈래 분할

병합은 정렬 뒤에 합쳤습니다. 퀵 정렬은 기준값으로 먼저 나누고 각 부분을 정렬합니다. 목표는 피벗 선택과 동률 처리가 재귀 크기에 어떤 영향을 주는지 이해하는 것입니다. 재귀와 분할 정복을 복습하세요.

개념과 약속

피벗은 분할 기준값입니다. 아래 교육용 구현은 가운데 위치의 값을 골라 작은 값·같은 값·큰 값의 새 목록 셋을 만듭니다. 작은 쪽과 큰 쪽만 재귀로 정렬하고 같은 값은 그대로 사이에 둡니다. 중복값을 별도로 묶어 모두 같은 입력에서 불필요한 재귀를 막습니다.

이 버전은 왼쪽부터 목록을 만들고 동률 원소들을 그대로 모으므로 일관된 키 비교에서 안정성을 보존합니다. 일반적인 제자리 퀵 정렬은 안정적이지 않은 경우가 많습니다. 이름이 같아도 이 코드에 적용할 설명과 흔한 구현의 성질을 구분해야 합니다. 가운데 위치의 값이 데이터의 중앙값이라는 보장은 없습니다.

손으로 상태 추적하기

작은 구간의 결과 [1,2]와 동률 [3,3], 큰 구간 [4]를 연결하면 [1,2,3,3,4]입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

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


print(quick_sort([4, 2, 3, 1, 3]))
print(quick_sort([2, 2, 2]))
print(quick_sort([]))

실행 결과:

[1, 2, 3, 3, 4]
[2, 2, 2]
[]

왜 맞고 언제 끝나는가

각 값은 비교 결과에 따라 셋 중 하나에 정확히 들어갑니다. 작은 쪽의 모든 값은 피벗보다 작고 큰 쪽은 큽니다. 재귀 결과 각각이 정렬되면 연결한 전체도 정렬됩니다. 입력에 존재하는 피벗과 같은 값 하나 이상이 동률 구간으로 분리되어 재귀 구간은 엄격히 작아집니다.

비용과 적용 범위

균형 있게 나뉘면 O(n log n), 계속 한쪽으로 쏠리면 O(n²) 시간입니다. 이 목록 복사 버전은 제자리 공간 O(log n)이라고 주장할 수 없습니다. 균형 재귀의 최고 추가 목록 공간은 O(n) 규모지만 편향된 호출에서 부모 목록들이 살아 있어 최악 O(n²) 공간과 O(n) 호출 깊이가 생길 수 있습니다. 큰 자료에서는 검증된 정렬을 사용하세요.

스스로 풀어 보기

1. 모든 값이 7인 목록에서 재귀는 어떤 구간으로 이어지나요?
2. 가운데 위치를 고르면 언제나 균형 분할이라는 주장이 왜 틀린가요?

힌트

1. 같은 값 구간만 길고 양쪽은 비어 있습니다.
2. 인덱스 위치와 값의 순위를 구분하세요.

해설

1. 양쪽 빈 목록이 기저 사례로 끝납니다. 동률 목록을 다시 정렬하지 않습니다.
2. 가운데 위치에 최솟값을 놓을 수 있습니다. 이때 작음은 비고 큼에 나머지가 몰립니다. 좋은 피벗은 값의 분포에 관한 조건입니다.

흔한 오해

퀵 정렬의 평균 설명을 특정 입력의 최악 보장으로 바꾸면 안 됩니다. 무작위 피벗이나 중앙값 근사 전략의 전제도 별도로 설명해야 합니다.

복습과 다음 연결

힙은 큰 값을 빠르게 꺼내기 위한 다른 구조입니다. 최악 시간 보장이 필요하면 힙 정렬도 비교합니다.