퀵정렬 시각화
피벗을 기준으로 배열을 분할하고 재귀적으로 정렬하는 과정을 관찰합니다
정렬★★☆
속도
1 / 1재귀 깊이: 0비교 횟수: 0스왑 횟수: 0
배열 크기20
피벗비교 중스왑최종 위치미정렬파티션 범위
피벗 선택과 파티션 과정을 단계별로 관찰하세요.
피벗 선택과 파티션 과정을 단계별로 관찰하세요.
퀵정렬이란?
퀵정렬(Quick Sort)은 분할정복 전략을 사용하는 고성능 정렬 알고리즘입니다. 피벗(기준값)을 선택하고, 피벗보다 작은 요소와 큰 요소로 배열을 분할한 후, 각 부분을 재귀적으로 정렬합니다. 평균적으로 O(n log n)의 시간 복잡도를 가집니다.
사용 방법
- 1배열 크기를 슬라이더로 조절하세요 (5~50)
- 2랜덤, 거의 정렬, 역순 버튼으로 다양한 입력을 생성하세요
- 3보라색 막대가 현재 피벗입니다
- 4연보라 배경이 현재 파티션 범위를 나타냅니다
- 5초록색 막대는 최종 위치가 확정된 요소입니다
동작 원리
- 1피벗(pivot) 선택 — 보통 마지막 요소, 랜덤, 또는 중위값을 선택합니다
- 2파티션: 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다
- 3피벗을 올바른 위치에 배치합니다
- 4왼쪽/오른쪽 부분 배열에 재귀적으로 동일 과정을 반복합니다
- 5부분 배열 크기가 1 이하면 종료됩니다
실무 활용
- •C 표준 라이브러리 qsort(), Java Arrays.sort()(기본형)의 기반 알고리즘입니다
- •대용량 데이터 정렬의 기본 선택 — 평균 O(n log n)에 캐시 효율이 좋습니다
- •데이터베이스 엔진의 정렬 연산에서 활용됩니다
- •분할정복의 대표 예제로 알고리즘 수업 필수 학습 항목입니다
- •병렬 퀵정렬 — 파티션 후 좌우를 병렬 처리할 수 있습니다
비슷한 알고리즘
- •병합정렬 vs 퀵정렬 — 병합정렬은 항상 O(n log n) 보장되지만 O(n) 추가 메모리 필요. 퀵정렬은 제자리(in-place)지만 최악 O(n²)
- •힙정렬 — 항상 O(n log n)에 제자리 정렬이지만 캐시 미스가 많아 실측 속도는 퀵정렬보다 느림
- •인트로정렬(Introsort) — 퀵정렬 + 힙정렬 조합. 재귀 깊이가 깊어지면 힙정렬로 전환하여 최악 O(n log n) 보장. C++ std::sort()가 이 방식
학습 팁
- •피벗이 배치된 후에는 해당 위치가 확정됩니다 (다시 이동하지 않음)
- •역순 배열에서 마지막 요소를 피벗으로 선택하면 최악의 경우(O(n²))가 됩니다
- •재귀 깊이가 깊을수록 더 작은 부분 배열을 처리하고 있습니다
- •랜덤 배열에서는 평균 O(n log n)에 가까운 성능을 보입니다
자주 묻는 질문
Q. 퀵정렬은 안정 정렬인가요?
A. 아닙니다. Lomuto/Hoare 파티션 모두 같은 값의 상대적 순서를 보장하지 않습니다. 안정 정렬이 필요하면 병합정렬을 사용하세요.
Q. 시간 복잡도는 어떻게 되나요?
A. 평균 O(n log n), 최악 O(n²) (이미 정렬된 배열 + 끝 피벗). 랜덤 피벗이나 중위값 피벗으로 최악 케이스를 피할 수 있습니다.
Q. 버블정렬과 비교하면?
A. 퀵정렬은 평균적으로 훨씬 빠릅니다(O(n log n) vs O(n²)). 실무에서 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.