퀵 셀렉트 (Quickselect)

"시험 성적 300개 중 중앙값만 알고 싶다" — 이럴 때 전체를 정렬(O(n log n))하는 건 낭비다. 퀵 셀렉트는 퀵 정렬의 절반만 써서 평균 O(n)에 k번째로 작은 값을 찾는다.

1. 정렬은 너무 많은 일을 한다

k번째로 작은 값 하나만 필요한데 전체를 정렬하면, 나머지 n-1개의 순서까지 전부 확정해 버린다. 필요 없는 정보다.

퀵 정렬을 떠올려 보자. 피벗 하나를 골라 배열을 "피벗보다 작은 것들 | 피벗 | 피벗보다 큰 것들"로 나누면(파티션), 피벗은 자기 최종 자리에 놓인다. 그 자리가 인덱스 p라면:

• p == k-1 → 피벗이 바로 답이다. 끝.
• p > k-1 → 답은 왼쪽 조각에 있다. 오른쪽은 통째로 버린다.
• p < k-1 → 답은 오른쪽 조각에 있다. 왼쪽을 버린다.

퀵 정렬은 양쪽을 모두 재귀하지만, 퀵 셀렉트는 한쪽만 파고든다. 이 차이가 O(n log n)을 O(n)으로 바꾼다.

2. 직접 돌려 보기

「한 단계 →」를 누르며 진행해 보자. 보라 막대가 피벗, 주황 테두리가 지금 비교 중인 원소, 초록 눈금이 우리가 찾는 위치 k-1이다. 흐려진 막대는 이미 버려진 구간이다.

3. 코드 — 파티션 + 한쪽 재귀

def quickselect(a, k):            # k: 1-based 순위
    lo, hi, target = 0, len(a) - 1, k - 1
    while lo < hi:
        p = partition(a, lo, hi)     # 피벗을 제자리에, 그 인덱스 반환
        if   p == target: return a[p]
        elif p <  target: lo = p + 1   # 오른쪽 조각만 남긴다
        else:             hi = p - 1   # 왼쪽 조각만 남긴다
    return a[lo]

def partition(a, lo, hi):          # Lomuto 방식, 피벗 = 마지막 원소
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]        # 피벗을 경계(i)로
    return i

재귀 대신 while 루프로 lo/hi만 좁혀 가므로 추가 스택도 필요 없다(O(1) 공간).

4. 왜 평균 O(n)일까

피벗이 운 좋게 매번 구간을 절반으로 나눈다고 하면, 훑는 양이 n + n/2 + n/4 + n/8 + … 이다. 이 무한합은 2n 으로 수렴한다.

퀵 정렬이 O(n log n)인 건 각 단계에서 양쪽 모두를 처리해 매 레벨이 다시 n이 되고, 레벨이 log n개이기 때문이다. 퀵 셀렉트는 레벨마다 일이 절반으로 줄어 총합이 상수배 n에 그친다.

최악의 경우 O(n²)

이미 정렬된 배열에서 항상 끝 원소를 피벗으로 쓰면, 구간이 1씩만 줄어 n + (n-1) + (n-2) + … = O(n²). 해결책:

• 무작위 피벗: 매번 구간에서 임의 원소를 골라 마지막과 교환 → 기대 O(n). (실무 표준)
• median-of-medians: 5개씩 묶어 중앙값들의 중앙값을 피벗으로 → 최악에도 O(n). 상수가 커서 보통은 무작위 피벗을 쓴다.
• introselect: 무작위 퀵 셀렉트로 시작하되, 재귀가 너무 깊어지면 힙 기반 O(n log k) 선택으로 전환. std::nth_element가 이 방식.

5. 다른 방법과 비교