다음 과정을 통해 수행되는 정렬 알고리즘의 특징으로 옳지 않은 것은?초… | [계리직 컴퓨터일반] 21년 1회차 기출문제 상세 페이지
1[계리직 컴퓨터일반] 21년 1회차
다음 과정을 통해 수행되는 정렬 알고리즘의 특징으로 옳지 않은 것은?
| 초기값 | 15 | 9 | 8 | 1 | 4 |
|---|---|---|---|---|---|
| 1단계 | 9 | 15 | 8 | 1 | 4 |
| 2단계 | 8 | 9 | 15 | 1 | 4 |
| 3단계 | 1 | 8 | 9 | 15 | 4 |
| 4단계 | 1 | 4 | 8 | 9 | 15 |
1
최악의 경우에 시간 복잡도는 O(n2)이다.
2
원소 수가 적거나 거의 정렬된 경우에 효과적이다.
3
선택정렬(selection sort)에 비해 비교연산 횟수가 같거나 적다.
4
정렬 대상의 크기만큼 추가 공간이 필요하다.
해설
옳지 않은 것은 정렬 대상의 크기만큼 추가 공간이 필요하다는 설명이다.
각 단계에서 앞쪽의 정렬된 부분에 다음 원소를 알맞은 위치로 끼워 넣고 있으므로 삽입 정렬이다. 삽입 정렬은 배열 안에서 원소를 옮기며 정렬하는 제자리 정렬이라 상수 크기의 추가 공간만 쓴다.
- 최악의 경우 시간 복잡도: 역순으로 정렬된 입력이면 매번 앞 원소 전부와 비교·이동하므로 이다.
- 원소 수가 적거나 거의 정렬된 경우: 이미 정렬된 부분에서 비교가 곧 끝나 거의 에 가까워지므로 효과적이다.
- 선택 정렬과의 비교 횟수: 선택 정렬은 항상 번 비교하지만 삽입 정렬은 그 이하이므로 같거나 적다.
오류나 개정된 내용이 보이면 알려주세요