병합(merge) 정렬과 퀵(quick) 정렬에 대한 설명으로 옳지 않… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
병합(merge) 정렬과 퀵(quick) 정렬에 대한 설명으로 옳지 않은 것은?
1
병합 정렬과 퀵 정렬은 모두 재귀 함수(recursive function)로 구현할 수 있다.
2
병합 정렬과 퀵 정렬은 모두 분할 정복(divide-and-conquer) 알고리즘에 속한다.
3
퀵 정렬은 병합 정렬과 달리 배열 내 요소 간 데이터를 교환 (swap)하지 않는다.
4
퀵 정렬은 입력의 피봇(pivot) 값을, 병합 정렬은 중간 위치를 사용하여 배열을 분할한다.
해설
퀵 정렬은 피봇을 기준으로 원소를 좌우로 나누는 과정에서 교환(swap)을 반복하므로, 교환하지 않는다는 설명이 옳지 않다.
오히려 병합 정렬이 교환 대신 보조 배열에 원소를 복사·병합하는 방식이다.
- 두 정렬은 부분 배열에 자기 자신을 다시 호출하는 재귀 함수로 구현할 수 있다.
- 두 정렬 모두 분할 → 정복 → 결합의 분할 정복 구조다.
- 퀵 정렬은 피봇 값에 따라, 병합 정렬은 중간 위치에서 배열을 나눈다.
오류나 개정된 내용이 보이면 알려주세요