퀵 정렬은 피벗을 기준으로 원소를 분할하고 각 부분을 재귀적으로 정렬하는 알고리즘이다.
원리
분할이 균형적이면 평균적인 실행 비용은 O(n log n)이지만, 나쁜 분할이 반복되면 O(n²)이 된다. 무작위화는 특정 입력 순서의 영향을 줄이는 방법이다.
예시
피벗 5를 기준으로 작은 값과 큰 값을 나누면 피벗을 사이에 두고 각 부분을 독립적으로 정렬할 수 있다. 같은 값이 많다면 세 부분 분할도 고려한다.
주의할 점
일반적인 제자리 구현은 안정 정렬이 아니다. 피벗 선택, 재귀 깊이와 중복 키 처리가 실제 성능에 큰 영향을 준다.