1. 알고리즘(30점)
<문제>
제시된 <그림>은 인접 비교방식을 통한 정렬 알고리즘의 일종이다. 즉 버블 정렬 기법을 응용하여 한번은 왼쪽에서 오른쪽으로 진행 하면서 최대 값을 우측으로 보내고, 한번은 오른쪽에서 왼쪽으로 진행하면서 최소 값을 좌측으로 보내는 방법을 반복하면서 정렬하는 기법이다. 이 알고리즘을 이용하여 크기가 4인 배열에 저장되어 있는 4개의 정수를 오름차순으로 정렬하고자 한다.
<그림>의 괄호 안 내용 (1)~(5)에 가장 적합한 항목을 <답항보기>에서 선택하여 답안지의 해당 번호 (1)~(5)에 각각 마크하시오.
<처리조건>
(1) <그림>의 순서도에 제시되어 있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 선택시 유의하시오.
(2) 배열의 크기가 4일 경우 배열의 요소는 0부터 3까지 구성된다. 예를 들어, A라는 배열의 크기가 4일 경우 배열의 요소는 A[0]부터 A[3]로 구현된다고 가정한다.
(3) <그림> 및 <답항보기>에서 부등호 기호
“>=”는 부등호 좌측의 값이 우측의 값보다 크거나 같다는 의미이고,
“<=”는 작거나 같다는 의미이고,
“>”는 크다는 의미이고,
“<”는 작다는 의미이며,
“<>”는 같지 않다 의미이다.
<순서도>
<답항보기>
|
1
|
d[i]
|
2
|
d[i]>d[left]
|
3
|
d[i]>d[left-1]
|
4
|
d[i]<=d[i+1]
|
5
|
d[i]
|
|
6
|
d[i]>=d[i-1]
|
7
|
d[i]>d[i+1]
|
8
|
d[i]>buf
|
9
|
d[i]>d[i-1]
|
10
|
d[i+1]
|
|
11
|
d[i+1]>d[i-1]
|
12
|
d[i-1]>d[i]
|
13
|
d[i+1]>buf
|
14
|
d[i-1]>d[right]
|
15
|
d[i-1]>d[right+1]
|
|
16
|
d[i-1]>d[right-1]
|
17
|
d[i+1]=d[i]
|
18
|
right=right-1
|
19
|
left<>right
|
20
|
left=left+i
|
|
21
|
left=left-1
|
22
|
left=left-i
|
23
|
left=right
|
24
|
left=d[i]
|
25
|
right=shift
|
|
26
|
shift=right-left
|
27
|
right=d[i]
|
28
|
right=i+buf
|
29
|
right=right+1
|
30
|
right=right+i
|
|
31
|
i=left
|
32
|
right=right-i
|
33
|
left=i
|
34
|
shift=i+1
|
35
|
shift=i-1
|
|
36
|
shift=left+right
|
37
|
shift=left-right
|
38
|
shift=right+1
|
39
|
shift=right-1
|
40
|
left=shift
|
<정답>
1. i = left
2. d[i] > d[i + 1]
3. right = shift
4. d[i – 1] > d[i]
5. left = shift
<순서도 정답>
<설명>
위 순서도를 C#으로 옮겨본 소스 코드는 아래와 같다.
위 코드를 Ctrl+F5번을 눌러 실행하면, 3, 2, 4, 1의 4개의 데이터를 입력했을 때, 실행 결과 1, 2, 3, 4순으로 정상적으로 오름차순 정렬됨을 알 수 있다.
끝.