---
title: "퀵 정렬: 피벗 선택과 분할 모양이 성능을 바꾸는 과정"
author: "Lee"
published_at: "2026-10-08T04:19:03.014Z"
updated_at: "2026-09-30T09:44:26.320Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%ED%80%B5-%EC%A0%95%EB%A0%AC-%ED%94%BC%EB%B2%97-%EC%84%A0%ED%83%9D%EA%B3%BC-%EB%B6%84%ED%95%A0-%EB%AA%A8%EC%96%91%EC%9D%B4-%EC%84%B1%EB%8A%A5%EC%9D%84-%EB%B0%94%EA%BE%B8%EB%8A%94-%EA%B3%BC%EC%A0%95"
ai_assisted: false
---

# 퀵 정렬: 피벗 선택과 분할 모양이 성능을 바꾸는 과정

[원문](https://ariser.io/@writer_a1cd615ab19e/%ED%80%B5-%EC%A0%95%EB%A0%AC-%ED%94%BC%EB%B2%97-%EC%84%A0%ED%83%9D%EA%B3%BC-%EB%B6%84%ED%95%A0-%EB%AA%A8%EC%96%91%EC%9D%B4-%EC%84%B1%EB%8A%A5%EC%9D%84-%EB%B0%94%EA%BE%B8%EB%8A%94-%EA%B3%BC%EC%A0%95)

퀵 정렬은 피벗을 기준으로 작은 원소와 큰 원소를 나누고, 각 부분을 다시 정렬한다. 피벗이 최종 위치에 놓이거나 피벗과 같은 구간이 확정되면 그 부분은 다시 정렬할 필요가 없다. 핵심은 원소를 어떤 분할 규칙으로 배치하는가다.

![피벗 5를 기준으로 3·1과 8·7이 양쪽에 배치된 퀵 정렬의 분할](/api/v1/media/45229d85-2cbc-497c-8e5d-235226e4c62f)

*분할 직후 양쪽 구간 내부까지 정렬된 것은 아니다.*

### 간단한 분할을 정확히 읽기

다음 Lomuto 분할은 반열린 구간 [start,end)의 마지막 값을 피벗으로 쓴다. 경계 앞은 피벗보다 작거나 같은 원소, 경계 뒤에서 현재 검사 위치 앞은 큰 원소라는 불변식을 유지한다.

```python
def partition(values, start, end):
    pivot = values[end - 1]
    boundary = start
    for scan in range(start, end - 1):
        if values[scan] <= pivot:
            values[boundary], values[scan] = values[scan], values[boundary]
            boundary += 1
    values[boundary], values[end - 1] = values[end - 1], values[boundary]
    return boundary
```

호출자는 길이가 2 이상일 때 분할하고, 피벗 위치 p를 제외한 [start,p), [p+1,end)를 처리한다. p를 다시 포함하면 종료가 안 될 수 있다. Hoare 방식은 반환 경계의 의미가 달라 같은 재귀 범위를 그대로 사용할 수 없다.

[4,1,3,2]에서 피벗 2를 쓰면 1이 왼쪽으로, 3과 4는 오른쪽으로 가고 2가 두 부분 사이에 자리 잡는다. 내부 구간은 아직 정렬되지 않았지만 양쪽과 피벗 사이의 순서 관계는 확보됐다.

### 평균이 빠르고 최악이 느린 이유

분할이 균형 잡히면 T(n)=2T(n/2)+O(n)으로 O(n log n)이다. 매번 한쪽에 n-1개가 남으면 n+(n-1)+… 작업을 하여 O(n²)이다. 마지막 원소 피벗으로 이미 정렬된 배열을 처리하면 이런 나쁜 분할이 반복될 수 있다.

무작위 피벗은 입력 순서와 나쁜 선택의 상관을 줄여 기대 O(n log n)을 얻는다. 최악 O(n²) 가능성이 사라진다는 뜻은 아니다. 같은 값이 많은 입력에는 작은 값·같은 값·큰 값 세 구간으로 나누는 방식이 효과적이다.

배열의 원소를 교환하는 전형적 구현은 데이터 보조 공간이 작지만 호출 스택은 평균 O(log n), 최악 O(n)이 될 수 있다. 작은 쪽만 재귀하고 큰 쪽을 반복 처리하면 스택 깊이를 제한할 수 있다. 보통 원소 교환으로 동일 키 순서가 바뀌어 안정 정렬은 아니다.

실제 라이브러리는 작은 구간 처리, 피벗 전략, 깊이 제한 뒤 다른 정렬로 전환하는 기법을 결합한다. 퀵 정렬을 평가할 때는 이름 하나보다 분할 규칙과 중복 키 처리, 최악 입력 대응을 확인해야 한다.

피벗과 같은 값을 항상 한쪽에 보내면 모든 원소가 같은 배열에서도 분할이 퇴화할 수 있다. 랜덤 피벗만으로 중복 키 문제가 모두 해결되지는 않는다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Quicksort](https://algs4.cs.princeton.edu/23quicksort/)