2025-07-30 22:11

Status:

Tags: 알고리즘

퀵 정렬

• 분할(partition) 정복(conquer) 분할 정복 이라는 단순하지만 강력한 아이디어 적용
• 큰 문제를 작은 단위로 나눈 후 작은 문제들을 재귀적으로 해결

구조

1. 피벗 선택 : 고르는 방법은 겁나 많음
2. 분할
   1. 피벗보다 작은건 왼쪽, 큰건 오른쪽
   2. 피벗을 기준으로 정렬 위치 확보
3. 정복(재귀 호출)
   1. 피벗 기준 좌우 부분에 같은 과정 반복
   2. 서브배열 1이하 되면 끝

파이썬 코드 구현

2.2 파티셔닝 구현 예시 (파이썬)

평균 시간 복잡도	최악 시간 복잡도	공간 복잡도
$O(n\log n)$	$O(n^2)$	$O(\log n)$*
비교 기반 정렬 중에선 최강자 라인업
분할 후 정복을 쓴다는 점에선 합병 정렬과 동일

다만 합병 정렬은 언제나 절반으로 나누고 퀵정렬은 피봇 쓰는등 아래같은 차이 있음

구분	합병 정렬	퀵정렬
분할 방식	항상 절반으로 균등 분할5	피벗 기준으로 불균등 분할 가능6
정복 방식	분할 후 각각 정렬5	분할 과정에서 동시에 정렬6
결합 방식	정렬된 두 부분 배열을 병합5	별도 결합 과정 불필요6
핵심 연산	병합(Merge)	분할(Partition)

References

배열 합병 정렬 분할 정복 퀵 정렬 핸드북