다음은 배열 A에 저장된 n개의 정수를 오름차순으로 정렬하는 삽입 정렬… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
다음은 배열 A에 저장된 n개의 정수를 오름차순으로 정렬하는 삽입 정렬(insertion sort) 알고리즘이다. ㉠과 ㉡에 순서대로 들어갈 내용으로 옳은 것은?void sort(int A[ ], int n)
{
int i, j, key;
for (i = 1; i < n; i++) {
key = A[i];
for (j = i - 1; ㉠ ; j--)
㉡
A[j+1] = key;
}
}
㉠ ㉡
1
j >= 0 && key > A[j] A[j+1] = A[j];
2
j > 0 && key >= A[j] A[j-1] = A[j];
3
j > 0 && key < A[j] A[j] = A[j+1];
4
j >= 0 && key < A[j] A[j+1] = A[j];
해설
㉠에는 j >= 0 && key < A[j], ㉡에는 A[j+1] = A[j];가 들어간다.
오름차순 삽입 정렬은 key보다 큰 원소를 한 칸씩 오른쪽으로 밀고, 멈춘 위치의 다음 칸 A[j+1]에 key를 넣는다. 맨 앞 A[0]까지 비교해야 하므로 j >= 0 조건이 필요하다.
- key > A[j] 조건으로 미는 조합: key보다 작은 원소를 밀게 되어 내림차순이 된다.
- j > 0 과 A[j-1] = A[j] 조합: A[0]과 비교하지 못하고, 원소를 왼쪽으로 옮겨 값을 덮어쓴다.
- j > 0 과 A[j] = A[j+1] 조합: A[0]과 비교하지 못하고, 이동 방향이 반대라 큰 원소가 오른쪽으로 밀리지 않는다.
오류나 개정된 내용이 보이면 알려주세요