퀵 정렬로 무작위 데이터는 빠르게 처리했지만 정렬된 입력에서는 급격히 느려집니다. 피벗과 분할이 어떤 영향을 주며 최악의 경우를 어떻게 줄이나요?

퀵 정렬의 성능은 피벗이 배열을 얼마나 균형 있게 나누는지에 크게 좌우됩니다. 분할마다 양쪽 크기가 비슷하면 깊이가 로그 수준이고 전체 비용이 평균적으로 O(n log n)에 가깝지만, 한쪽에 거의 모든 원소가 남으면 매 단계 비슷한 구간을 다시 훑어 O(n²)까지 커질 수 있습니다. 정렬 입력에서 첫 원소를 피벗으로 고르는 구현은 대표적인 최악 반례입니다.

최악 지연과 스택을 함께 제한합니다

1, 2, 3, 4에서 첫 원소를 피벗으로 잡으면 왼쪽은 비고 오른쪽에 나머지가 남습니다. 다음 호출도 같은 일이 반복되어 비교 수가 4+3+2처럼 누적됩니다. 역정렬 입력도 반대 방향으로 같은 문제를 만듭니다. 무작위 피벗, 중간값의 근사, median-of-three는 특정 패턴이 계속 나올 가능성을 낮추지만 모든 입력에서 최악을 제거한다는 뜻은 아닙니다. 이를 불균형 분할(unbalanced partition)로 인한 최악 경로라고 부릅니다.

같은 값이 많으면 두 구간만 만드는 분할이 같은 값과 계속 비교할 수 있습니다. < pivot, == pivot, > pivot의 세 구간으로 나누는 3-way partition이 중복이 많은 입력에서 유리할 수 있습니다. 비교자가 일관된 strict weak ordering을 제공하지 않으면 피벗 정책과 무관하게 정렬 결과가 정의되지 않을 수 있습니다.

직접 구현하기보다 표준 라이브러리의 시간·메모리·안정성 보장을 확인하겠습니다. introsort처럼 재귀 깊이가 임계값을 넘으면 힙 정렬로 전환하는 방식은 평균 퀵 정렬의 장점과 O(n log n) 최악 상한을 결합하려는 전략입니다. 작은 구간에서는 삽입 정렬이 비교와 분기 비용이 작아 유리할 수 있습니다. 재귀 깊이 제한은 실행 시간뿐 아니라 호출 스택 고갈을 막는 안전 조건입니다.

테스트는 정렬·역정렬·무작위·동일 값·이미 거의 정렬된 입력과 공격적인 패턴을 포함합니다. 평균 시간만 보지 않고 비교 횟수, 최대 재귀 깊이, p99, 임시 메모리, 입력 복사 여부를 기록하겠습니다. 무작위 피벗은 확률적 완화이지 절대 보장이 아니며, 애플리케이션의 최악 지연 요구가 강하면 보장된 라이브러리나 다른 정렬을 선택하겠습니다.

퀵 정렬은 피벗을 기준으로 구간을 나누며, 균형 분할이면 평균 O(n log n)에 가깝지만 한쪽 구간이 n-1개씩 남으면 O(n²)이 됩니다. 정렬 배열에서 첫 원소를 계속 피벗으로 고르는 것이 대표적인 반례입니다. 같은 값이 많으면 <, ==, > 세 구간으로 나누는 3-way partition이 비교를 줄일 수 있지만 비교자의 순서 계약을 대신해 주지는 않습니다.

재귀 스택을 제한할 때는 작은 구간을 먼저 재귀 처리하고 큰 구간은 반복으로 남겨 깊이를 로그 수준으로 제한합니다. 명시적 스택을 쓴다면 큰 구간을 push하고 작은 구간을 먼저 처리하는 식으로 스택의 최대 크기를 줄일 수 있습니다. 무작위 피벗은 기대 성능을 완화할 뿐 최악을 제거하지 않으므로, introsort 전환·입력 크기 제한·표준 라이브러리 보장을 정렬·동일값·공격 패턴에서 비교하겠습니다.

분할 후 왼쪽·오른쪽 구간이 반드시 줄어드는지도 확인하겠습니다. 같은 값만 있는 입력에서 두 포인터가 멈춘 채 다시 같은 구간을 재귀 호출하면 최악 시간 이전에 무한 반복이 생깁니다. 분할 함수의 반환 경계가 피벗의 최종 위치인지 구간 경계인지에 따라 재귀 범위가 다르므로, 서로 다른 partition 방식의 호출 코드를 섞지 않겠습니다.