[알고리즘] 퀵 정렬(Quick Sort) 동작 원리와 시간 복잡도 분석: 피벗 선택과 분할 정복
TL;DR (세 줄 요약)
- 퀵 정렬은 평균 O(n log n)으로 빠른 정렬 알고리즘입니다. 하지만 피벗(기준 값)을 잘못 고르면 이미 정렬된 배열에서 O(n²)까지 느려집니다.
- 피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 두 구간에 같은 일을 반복합니다. 한쪽으로만 나뉘면 비교 횟수가 (n-1)+(n-2)+…+1이 되어 n의 제곱에 비례합니다.
- 무작위 피벗, 미디언-오브-쓰리, 작은 구간의 삽입 정렬 전환, 재귀 깊이 줄이기, Introsort로 최악의 경우를 피합니다.
한 기업의 필기 테스트에서 나온 문제를 계기로 퀵 정렬을 다시 정리했습니다. 정렬은 값을 크기 순서대로 늘어놓는 일입니다. 이 글은 퀵 정렬의 기본 개념, 동작 원리, 최악의 경우가 생기는 이유, 그것을 줄이는 방법을 순서대로 설명합니다.

1. 퀵 정렬은 무엇인가요?
퀵 정렬은 분할 정복 방식의 정렬입니다. 분할 정복은 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 배열에서 기준 값을 하나 고르고, 그 값보다 작은 것과 큰 것을 양쪽으로 나눈 뒤, 나뉜 두 구간에 같은 일을 반복합니다. 이 기준 값을 피벗(pivot)이라고 부릅니다.
- 피벗 선택: 배열에서 값을 하나 고릅니다. 보통 첫 값, 마지막 값, 또는 무작위로 고른 값을 씁니다.
- 분할: 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮깁니다. 분할이 끝나면 피벗의 최종 위치가 정해집니다.
- 재귀: 왼쪽 구간과 오른쪽 구간에 같은 과정을 반복합니다. 구간의 길이가 1 이하이면 멈춥니다. 재귀는 함수가 자기 자신을 다시 호출하는 방식입니다.
퀵 정렬의 특징은 다음과 같습니다.
- 평균 시간 복잡도가 O(n log n)입니다. 실제 데이터에서 대체로 매우 빠릅니다.
- 제자리(in-place) 정렬입니다. 추가 배열 없이 원본 배열 안에서 값을 바꿉니다.
- 불안정 정렬입니다. 값이 같은 원소끼리의 원래 순서가 유지된다고 보장하지 않습니다.
- 정렬된 배열이나 역순 배열에서 한쪽 끝 값을 피벗으로 고르면 성능이 크게 떨어집니다.
2. 퀵 정렬은 어떻게 동작하나요?
아래 코드는 마지막 값을 피벗으로 쓰는 가장 단순한 형태입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 마지막 값을 피벗으로
int i = low - 1; // 작은 값이 놓일 자리의 끝
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
++i;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // 피벗을 자기 자리로
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
partition 함수가 하는 일
i는 피벗보다 작거나 같은 값이 모인 구간의 마지막 위치입니다. j가 배열을 한 칸씩 지나가다가 피벗보다 작거나 같은 값을 만나면, i를 1 늘리고 두 위치의 값을 바꿉니다. 반복이 끝나면 i + 1이 피벗이 들어갈 자리입니다. 그 왼쪽은 모두 피벗 이하이고, 오른쪽은 모두 피벗 이상입니다.
재귀가 끝나는 조건
구간의 길이가 1이면 이미 정렬된 상태이므로 아무것도 하지 않습니다. 그래서 low < high일 때만 재귀 호출을 합니다. 이 조건이 없으면 호출이 끝나지 않습니다.
3. 제자리 정렬은 무엇인가요?
제자리 정렬은 추가 배열을 만들지 않고 원본 배열 안에서 값을 바꿔 정렬하는 방식입니다. 메모리를 적게 쓰고, 값이 이어진 공간에 있어서 CPU 캐시(자주 쓰는 데이터를 빠르게 꺼내 쓰는 작은 저장 공간)를 잘 활용합니다. 퀵 정렬에는 병합 정렬과 달리 정렬된 두 구간을 합치는 단계가 없습니다.
4. 시간 복잡도는 얼마인가요?
시간 복잡도는 데이터 개수 n이 늘어날 때 계산 횟수가 얼마나 늘어나는지를 나타내는 표기입니다.
| 경우 | 복잡도 | 이유 |
| 평균과 최선 | O(n log n) | 분할이 절반씩 균형 있게 되면 단계마다 n번 비교하고, 단계 수가 log n입니다. |
| 최악 | O(n²) | 피벗이 매번 가장 작거나 가장 큰 값이면 한쪽에 n-1개, 그다음 n-2개가 남습니다. 비교 횟수가 (n-1)+(n-2)+…+1 = n(n-1)/2가 됩니다. |
| 공간 | 평균 O(log n), 최악 O(n) | 재귀 호출이 쌓이는 스택 메모리의 크기입니다. |
5. 최악의 경우는 언제 생기나요?
이미 오름차순으로 정렬된 배열 [1, 2, 3, 4, 5]에서 마지막 값을 피벗으로 고르는 경우를 보겠습니다. 첫 분할에서 피벗 5의 왼쪽에 4개가 남습니다. 다음 분할에서도 왼쪽에 3개가 남습니다. 이렇게 한쪽만 1개씩 줄어듭니다. 내림차순 배열에서 첫 값을 피벗으로 골라도 같은 일이 생깁니다.
거의 정렬된 데이터를 자주 다루는 프로그램에서는 이 경우가 드물지 않습니다. 그래서 피벗을 고르는 방법이 성능을 좌우합니다.
6. 최악의 경우는 어떻게 줄이나요?
무작위 피벗
int randomIndex = low + rand() % (high - low + 1);
swap(arr[randomIndex], arr[high]);
구간 안에서 위치를 무작위로 하나 골라 마지막 값과 바꾼 뒤 정렬합니다. 입력 순서 때문에 생기는 치우침이 없어집니다. 이미 정렬된 배열이 들어와도 피벗이 한쪽 끝 값일 확률이 낮아져 평균 성능에 가까워집니다.
미디언-오브-쓰리(median of three)
첫 값, 가운데 값, 마지막 값 중에서 크기가 중간인 값을 피벗으로 씁니다. 정렬된 배열에서도 가운데 값이 피벗이 되어 분할이 균형을 이룹니다.
작은 구간은 삽입 정렬로 바꾸기
구간의 길이가 10~16 정도로 작아지면 삽입 정렬로 바꿉니다. 정확한 기준은 구현마다 다릅니다. 작은 배열에서는 재귀 호출에 드는 비용이 정렬 자체보다 크기 때문입니다.
재귀 깊이 줄이기
두 구간 중 더 작은 쪽만 재귀로 호출하고, 더 큰 쪽은 반복문으로 이어서 처리합니다. 이렇게 하면 재귀 깊이가 log n 수준을 넘지 않습니다. 스택 메모리를 아끼고, 최악의 경우에도 스택이 넘치지 않습니다.
Introsort
퀵 정렬로 시작하되, 재귀 깊이가 log n의 일정 배수를 넘으면 힙 정렬로 바꿉니다. 힙 정렬은 최악의 경우에도 O(n log n)이므로 전체 성능의 한계가 보장됩니다. C++ 표준 라이브러리의 std::sort는 GCC의 libstdc++ 같은 주요 구현에서 이 방식으로 만들어져 있습니다.
7. 정리하면 무엇을 기억해야 하나요?
퀵 정렬은 평균 성능이 좋고 메모리를 적게 쓰지만, 피벗 선택에 따라 성능이 크게 달라집니다. 최악의 경우와 개선 방법을 함께 알고 있으면, 정렬을 직접 구현하거나 라이브러리 정렬의 동작을 판단할 때 도움이 됩니다. 코드를 작성한 것과 실제 입력에서 성능이 나오는 것은 다릅니다. 정렬된 데이터와 역순 데이터를 넣어서 비교 횟수를 직접 세어 보는 확인이 필요합니다.
자주 묻는 질문 (FAQ)
Q1. 퀵 정렬이 병합 정렬보다 항상 빠른가요?
아닙니다. 평균적으로는 퀵 정렬이 빠르고 메모리도 적게 씁니다. 다만 병합 정렬은 항상 O(n log n)이 보장되고 안정 정렬입니다. 최악의 경우를 피할 수 없거나 같은 값의 순서를 유지해야 하면 병합 정렬이 낫습니다.
Q2. 이미 정렬된 배열에서 왜 느려지나요?
마지막 값을 피벗으로 쓰면, 이미 정렬된 배열에서는 매번 가장 큰 값이 피벗이 됩니다. 분할이 한쪽으로만 되어 구간이 1개씩만 줄어들고, 비교 횟수가 n의 제곱에 비례해서 늘어납니다.
Q3. std::sort는 어떤 정렬인가요?
주요 구현에서는 Introsort입니다. 퀵 정렬로 시작하고, 재귀 깊이가 기준을 넘으면 힙 정렬로, 구간이 작으면 삽입 정렬로 바꿉니다. 그래서 평균은 빠르고 최악의 성능도 O(n log n)으로 제한됩니다.
수정 안내
이 글은 2026년 11월 21일에 다시 썼습니다. 재귀 깊이를 줄이는 방법에서 "더 큰 쪽을 재귀로 호출한다"고 적었던 것은 반대로 적은 것이어서, "더 작은 쪽을 재귀로 호출하고 큰 쪽은 반복문으로 처리한다"로 고쳤습니다. C++ 표준은 std::sort의 알고리즘을 정해 두지 않으므로 "주요 구현에서 Introsort"라고 고쳤습니다.
참고 자료
- Wikipedia: Quicksort
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd ed.)
- Musser, D. R., Introsort: a hybrid sorting algorithm, Software: Practice and Experience, 27(8), 1997
- C++ Reference, std::sort
같은 주제의 다른 글: [알고리즘] 최소 스패닝 트리(MST) 개념과 구현: 크루스칼 vs 프림 비교, [자료구조/C언어] 레드-블랙 트리(Red-Black Tree) 규칙·회전·삽입·삭제 정리, [데이터베이스] DB 인덱스(Index) 핵심 원리: B-Tree 구조와 검색 성능 최적화