분할 정복(divide-and-conquer) 방식의 정렬 알고리즘에 … | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
분할 정복(divide-and-conquer) 방식의 정렬 알고리즘에 대한 설명으로 옳지 않은 것은?
1
2-way 합병 정렬의 분할은 분할 대상을 반으로 나눈다.
2
퀵정렬(quick sort)의 분할은 분할 대상에 대하여 피봇(pivot)을 기준으로 나눈다.
3
합병 정렬과 다르게 퀵정렬에서는 모든 분할이 완료되면 정렬도 완료된다.
4
합병 정렬은 추가 데이터 저장공간이 필요 없는 제자리 정렬 알고리즘이다.
해설
옳지 않은 설명은 합병 정렬이 추가 저장공간이 필요 없는 제자리 정렬이라는 내용이다.
합병 정렬은 정렬된 두 부분 배열을 합칠 때 입력 크기만큼의 보조 배열이 필요하므로 제자리 정렬이 아니다.
- 2-way 합병 정렬은 분할 대상을 반으로 나누므로 옳다.
- 퀵 정렬은 피봇보다 작은 값과 큰 값으로 분할하므로 옳다.
- 퀵 정렬은 분할 과정에서 원소 위치가 확정되어 분할이 끝나면 정렬도 끝나지만, 합병 정렬은 분할 후 합병 단계에서 정렬이 이루어지므로 옳다.
오류나 개정된 내용이 보이면 알려주세요