퀵 정렬 (Quick Sort)

피벗을 골라 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 퀵 정렬을 막대 애니메이션으로 확인하세요. 평균 O(n log n)인데 역순 배열에서 O(n²)로 무너지는 이유를 직접 볼 수 있습니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

0

교환/쓰기

0

스텝

0/467

읽기

0

보조 메모리

0

재귀 깊이

1/1

재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.

의사코드

quickSort(lo, hi)

pivot ← a[hi]

for j ← lo to hi−1

if a[j] ≤ pivot: a[i++] ↔ a[j]

a[i] ↔ a[hi] // 피벗 확정

quickSort(lo,i−1) quickSort(i+1,hi)

시간 복잡도

최선O(n log n)
평균O(n log n)
최악O(n²)
공간O(log n)
안정X

퀵 정렬은 기준값(피벗)을 하나 골라, 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 모으는 분할(partition)을 반복하는 알고리즘입니다. 보라색이 현재 피벗이고, 분할이 끝나면 피벗의 최종 위치가 확정(초록)됩니다.

피벗이 매번 중간 근처를 가르면 분할 깊이가 log n이라 평균 O(n log n)이고, 캐시 지역성이 좋아 실제 속도는 O(n log n) 알고리즘 중 가장 빠른 편입니다. 대부분의 언어 내장 정렬이 퀵 계열을 기반으로 하는 이유입니다.

반면 피벗이 항상 최솟값·최댓값이면(예: 역순 배열에서 마지막 원소를 피벗으로 선택) 분할이 한쪽으로 치우쳐 O(n²)이 됩니다. '역순' 프리셋으로 실행하면 비교 횟수가 버블 정렬 수준으로 폭증하는 것을 확인할 수 있고, 이를 막는 랜덤 피벗·중앙값 기법이 실무에서 쓰입니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

퀵 정렬이 최악 O(n²)인데 왜 표준 정렬로 쓰이나요?
랜덤 피벗이나 세 값의 중앙값을 쓰면 최악 케이스 확률이 사실상 사라지고, 평균 성능과 캐시 효율이 다른 O(n log n) 알고리즘보다 좋기 때문입니다. 일부 구현은 나쁜 분할이 감지되면 힙 정렬로 전환합니다(Introsort).
퀵 정렬은 안정 정렬인가요?
아닙니다. 분할 과정에서 멀리 떨어진 원소끼리 교환하므로 같은 값의 상대 순서가 깨질 수 있습니다.
피벗은 어떻게 고르는 게 좋은가요?
첫/마지막 원소는 정렬된 입력에서 최악이 되므로, 중간 위치·랜덤·세 값의 중앙값(median-of-three)을 쓰는 것이 일반적입니다.

다른 알고리즘 보기