피벗을 골라 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 퀵 정렬을 막대 애니메이션으로 확인하세요. 평균 O(n log n)인데 역순 배열에서 O(n²)로 무너지는 이유를 직접 볼 수 있습니다.
알고리즘
배열
비교
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²)이 됩니다. '역순' 프리셋으로 실행하면 비교 횟수가 버블 정렬 수준으로 폭증하는 것을 확인할 수 있고, 이를 막는 랜덤 피벗·중앙값 기법이 실무에서 쓰입니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.