문제
퀵 정렬(Quick Sort)에 대한 설명으로 가장 옳지 않은 것은?
① 분할 정복 기법을 사용하는 정렬 알고리즘이다 ② 평균 시간 복잡도는 O(n log n)이지만 최악의 경우 O(n²)이다 ③ 피벗 선택 방법에 따라 성능이 크게 좌우된다 ④ 항상 안정 정렬(Stable Sort)을 보장한다
정답
4번
해설
퀵 정렬은 불안정 정렬(Unstable Sort)이다. 피벗을 중심으로 분할하는 과정에서 같은 값을 가진 원소들의 상대적 순서가 바뀔 수 있다.