정렬에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
정렬에 대한 설명으로 옳지 않은 것은?
1
배열에 저장되어 있는 자료들을 정렬할 경우, 합병정렬은 힙정렬보다 메모리 공간을 더 필요로 한다.
2
합병정렬로 n개의 자료를 정렬할 때, 정렬된 입력이나 그렇지 않은 입력이나 걸리는 시간은 항상 이다.3
배열에 저장되어 있는 n개의 자료를 정렬하는 선택정렬에서, 최악의 경우 자료 비교횟수는 이고 최악의 경우 배열에서의 자료이동 횟수도 이다.
4
정렬된 입력에 대하여 퀵정렬(첫 번째 원소를 기준으로 분할)은 힙정렬보다 시간이 많이 걸린다.
해설
옳지 않은 것은 선택정렬의 최악 자료이동 횟수도 라는 설명이다.
선택정렬은 비교가 이지만 각 단계에서 최솟값과 한 번만 교환하므로 자료 이동은 최악에도 이다.
- 합병정렬과 힙정렬의 공간: 배열 합병정렬은 크기 n의 보조 배열이 필요하지만 힙정렬은 제자리 정렬이므로 옳다.
- 합병정렬의 시간: 입력 상태와 관계없이 반씩 나누어 합병하므로 항상 으로 옳다.
- 정렬된 입력의 퀵정렬: 첫 원소를 기준으로 하면 분할이 한쪽으로 치우쳐 이 되어 인 힙정렬보다 느리므로 옳다.
오류나 개정된 내용이 보이면 알려주세요