문제
하나의 리스트를 기준값(pivot)을 기준으로 분할한 뒤 정렬을 반복하는 방식으로, 분할 정복 전략을 적용한 정렬 기법은?
① 삽입 정렬 ② 버블 정렬 ③ 퀵 정렬 ④ 선택 정렬
정답
3번
해설
정답: 3. 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값으로 분할한 뒤 재귀적으로 정렬을 수행한다.
오답 풀이
- 1번: 삽입 정렬은 앞쪽의 정렬 영역에 원소를 삽입하는 방식이다.
- 2번: 버블 정렬은 인접 원소들을 비교해 교환한다.
- 3번: 퀵 정렬은 피벗 기반의 분할 정복 정렬이다.
- 4번: 선택 정렬은 최소(또는 최대) 원소를 골라 위치를 바꾼다.
보충 개념 퀵 정렬의 평균 시간 복잡도는 O(n log n)이다.