정렬 알고리즘에 대한 설명으로 옳은 것은? | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 26년 1회차
정렬 알고리즘에 대한 설명으로 옳은 것은?
1
힙 정렬의 시간 복잡도는 이다.2
퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행한 후 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.
3
삽입 정렬은 입력에 민감한 알고리즘으로, 입력이 거의 정렬되어 있을 때 처리시간이 느리고, 입력이 역으로 정렬되어 있을 때는 최선의 경우로 빠르다.
4
병합 정렬은 크기가 n인 입력을 n/2 크기로 분할하고, 각각에 대해 같은 방식으로 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병한다.
해설
옳은 설명은 병합 정렬이 입력을 절반으로 분할해 각각 정렬한 뒤 합병한다는 것이다.
병합 정렬은 분할 정복 알고리즘으로, 분할 깊이 단계마다 합병을 하므로 이다.
- 힙 정렬은 최악의 경우에도 이다.
- 퀵 정렬은 정렬을 먼저 하는 것이 아니라, 기준값으로 먼저 분할한 뒤 각 부분집합을 재귀적으로 정렬한다.
- 삽입 정렬은 거의 정렬된 입력에서 빠르고(최선), 역순 입력에서 가장 느리다(최악).
오류나 개정된 내용이 보이면 알려주세요