Time and Space Complexity

시간 복잡도:

• 평균적인 경우: O(n log n)
  • 균형 잡힌 피벗은 매번 배열을 대략 절반으로 나누어, 약 log n 단계의 O(n) 분할 작업을 수행합니다.
• 최악의 경우: O(n²)
  • 피벗이 항상 가장 작거나 큰 요소인 경우(예: 마지막 요소를 피벗으로 사용하는 이미 정렬된 배열), 매번 한쪽이 비게 되어 재귀의 깊이가 n 단계가 됩니다.

공간 복잡도:

• 여기서 구현하는 버전의 경우 매 단계마다 새로운 작은 리스트와 큰 리스트를 생성하므로 O(n)입니다. 전통적인 제자리(in-place) 퀵 정렬은 이를 O(log n)의 추가 공간으로 개선합니다.

요약:

• 퀵 정렬은 평균적으로 매우 빠르며 실무에서 자주 사용되는 정렬 알고리즘입니다.
• 좋지 않은 피벗 선택은 성능을 O(n²)으로 저하시킬 수 있습니다. 좋은 피벗 전략(무작위 또는 중앙값 요소 선택 등)을 통해 이를 방지할 수 있습니다.