문제
수열 [39, 45, 26, 35, 54]를 삽입 정렬(Insertion Sort)할 경우 1회전 후 결과는?
① [26, 39, 45, 35, 54] ② [39, 45, 26, 35, 54] ③ [39, 26, 45, 35, 54] ④ [26, 35, 39, 45, 54]
정답
2번
해설
삽입 정렬(Insertion Sort)은 두 번째 원소부터 시작하여 그 앞(왼쪽)의 정렬된 부분과 비교하여 삽입할 위치를 찾는 알고리즘이다. 첫 번째 원소는 이미 정렬된 것으로 간주한다.
[1회전] Key = 45 (두 번째 원소)
- 정렬된 부분: [39]
- 45와 39 비교 → 45 > 39이므로 자리 이동 없음
- 결과: [39, 45, 26, 35, 54]
따라서 1회전 후 결과는 변화가 없는 [39, 45, 26, 35, 54]이다.
[참고: 이후 회전 결과]
- 2회전 (Key=26): [26, 39, 45, 35, 54]
- 3회전 (Key=35): [26, 35, 39, 45, 54]
- 4회전 (Key=54): [26, 35, 39, 45, 54] (정렬 완료)