Qck
SORTING
퀵 정렬 (Quick Sort)
기준값(pivot)을 정해 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 과정을 한 단계씩, 또는 자동 재생으로 직접 확인하세요. 평균은 가장 빠른 정렬 중 하나지만, pivot을 어떻게 고르느냐에 따라 최악의 경우가 달라진다는 점을 눈으로 비교할 수 있습니다.
재생 버튼을 눌러 정렬을 시작하세요.
비교 0회 · 교환 0회
1 / 1
속도
대기
기준값(pivot)
비교 중
교환됨
자리 확정
PSEUDOCODE (Lomuto partition)
quickSort(lo, hi): if lo < hi pivot ← array[hi] i ← lo - 1 for j ← lo to hi-1 if array[j] < pivot i++; swap(array[i], array[j]) swap(array[i+1], array[hi])어떻게 동작하나요
구간의 마지막 값을 기준값(pivot)으로 정하고, 나머지 값들을 훑으며 pivot보다 작은 값을 왼쪽으로 모읍니다. 훑기가 끝나면 pivot을 그 경계 자리로 옮겨 확정합니다 — 이 값보다 작은 값은 모두 왼쪽에, 큰 값은 모두 오른쪽에 있게 됩니다. 이제 왼쪽 구간과 오른쪽 구간에 대해 각각 같은 과정을 재귀적으로 반복합니다.
시간·공간 복잡도
- 최선
- O(n log n)
- 평균
- O(n log n)
- 최악
- O(n²)
- 공간 복잡도
- O(log n)
- 안정 정렬
- 아니오 (Not stable)
이 페이지는 항상 마지막 원소를 pivot으로 고정합니다 — 그래서 "정렬됨"·"역순" 프리셋 모두 최악의 경우 O(n²)가 됩니다. pivot을 무작위로 고르거나 중앙값을 쓰면 이 문제를 피할 수 있습니다.
다른 정렬 알고리즘(버블·선택·삽입·병합)도 함께 시각화되어 있습니다 — Algorithm 코스로 돌아가기