[기사기출]6. 삽입정렬 (07년2회)

정보처리기사 실기 - 기출문제 - 알고리즘- 삽입정렬 (07년2회 출제)

[문제]

제시된 <그림>은 100보다 작은 30개의 자연수가 배열 AR(30)에 정렬되지 않은 상태로 저장되어 있을 때 이 데이터를 오름차

순으로 정렬하는 삽입 정렬(Insertion Sort) 알고리즘을 나타낸 것이다.

<그림>의 괄호 안 내용에 가장 적합한 항목을 <답항 보기>에서 선택하여 해당 번호 (1)~(5)에 마크하시오.

<그림>에 제시되어 있는 알고리즘과 연계하여 가장 적합한 로직으로 구현될 수 있도록 답안 선택시 유의하시오.

배열의 크기가 n일 경우 배열의 요소는 1 부터 n 까지 구성되는 것으로 한다.

예를 들어, A라는 배열의 크기가 10 일 경우 A(10)으로 표시되고 배열 요소는 A(1) 부터 A(10) 으로 구현된다고 가정한다.

[답항보기]

1. M=2

-> (1)번 블랭크 밑에 보면 AR(m)이 사용되었습니다. 이때 m의 초기값이 없으므로 1번의 블랭크에는 m을 초기화 해줘야합니다. 이때 m=1이 아닙니다. 삽입정렬은 두번째자리부터 시작해야함으로 m=2 가 정답입니다.

2. M-1

-> (2)번 블랭크 밑에 보면 key > AR(w) 로 크기를 비교하고 있습니다. key값은 1번에서  AR(m)으로 넣어줬습니다. 그러면 삽입정렬할때 비교하기위한 key 앞자리의 값을 지정해줘야 함으로 m-1 인 자리의 위치를 w에 넣어줘야 합니다. 즉 w = m-1 이 됩니다.

3. AR(w+1) = AR(w)

-> (3)번 블랭크는 두수를 비교해서 앞의 수가 클경우 치환을 하는 부분입니다. 큰수인 AR(W)를 비교했던 뒷자리 AR(w+1) 자리로 옮겨줍니다. 즉 AR(w+1) = AR(w)가 됩니다. 

4. w >= 1

-> (4)번 블랭크는 비교하는 부분을 계속할지 여부를 판별하는 부분입니다. 마직막는 1번째 위치에 있는 것이므로 1 이하로는 비교할것이 없으므로 w >= 1 입니다. 순서도에서 비교문 yes일때 반복을 하고 no이면 반복을 끝내고 나가야 됨으로 부등호 방향이 w가 1보다 크거나 같다로 해야되는 것입니다. 

5. AR(w+1)

-> (5)번 블랭크는 비교문이 no일때 입니다. 그러면 w가 1보다 작을때 입니다. key값을 다시 넣어줘야 하는 데 w는 0이므로 AR(w+1)이 되야 합니다.