정답
㉠ \(b < \text{BUCKETS}\), ㉡ \(i < \text{cnt}\), ㉢는 각 자릿수에 대해 정렬을 반복하기 위해 \(factor\)를 10배씩 증가시키는 연산이며, 배열 \(a=\{86,48,25,45,67,35,22,82\}\) 에 대해 radix_sort(a, 8)을 호출했을 때 첫 번째 출력 줄은 \(22\ 82\ 25\ 45\ 35\ 86\ 67\ 48\) 이다.
출제 의도
큐를 이용한 기수 정렬(radix sort)의 동작 원리를 이해하고, 버킷의 개수와 자료의 개수에 따른 반복문 조건을 올바르게 채우는지를 평가한다. 또한 자릿수별로 정렬을 반복하기 위해 곱셈 연산으로 자리 수 선택 인자를 변경하는 이유와, 실제 예시 배열에 기수 정렬을 적용한 중간 결과를 구하는 능력을 묻는다.
풀이 과정
프로그램에서 BUCKETS는 10진수의 10개 버킷(0~9), cnt는 정렬할 원소 개수이다. 큐를 초기화하는 반복문
for(b = 0; ㉠ ; b++) init_queue(b);
에서는 버킷 번호 \(0\)부터 \(9\)까지 초기화해야 하므로 조건은 \(b < \text{BUCKETS}\) 이 되어야 한다. 따라서 ㉠에는 \(b < \text{BUCKETS}\) 가 들어간다.
다음으로, 각 단계에서 모든 원소를 해당 자릿수에 따라 큐에 넣는 반복문
for(i = 0; ㉡ ; i++) enqueue((list[i] / factor) % 10, list[i]);
에서는 배열의 모든 원소를 처리해야 하므로 인덱스 \(i\)가 \(0\)부터 \(\text{cnt}-1\)까지 순회해야 한다. 따라서 조건은 \(i < \text{cnt}\) 가 되어야 하므로, ㉡에는 \(i < \text{cnt}\) 가 들어간다.
정렬 과정에서 ㉢ 위치의 코드는
factor *= 10;
이다. 처음 factor는 1이므로,
$$ \frac{\text{list}[i]}{\text{factor}} \bmod 10 $$
은 일의 자리(1의 자리) 숫자를 의미한다. 한 번의 자릿수 정렬이 끝난 후 factor에 10을 곱해 10, 100, 1000, … 으로 바꾸면, 다음 반복에서 각각 십의 자리, 백의 자리, 천의 자리, … 를 뽑아낼 수 있다. 따라서 ㉢에서 곱셈 연산을 하는 이유는, 기수 정렬에서 낮은 자릿수부터 높은 자릿수로 순차적으로 정렬하기 위해 추출할 자릿수를 바꾸기 위함이다.
이제 주어진 배열
$$ a = \{86, 48, 25, 45, 67, 35, 22, 82\} $$
에 대해 radix_sort(a, 8)을 수행할 때 첫 번째 출력 줄을 구한다. 처음 factor = 1 이므로, 일의 자리를 기준으로 큐에 분배한다.
각 원소의 일의 자리는 다음과 같다.
$$ \begin{aligned} 86 &\rightarrow 6,\\ 48 &\rightarrow 8,\\ 25 &\rightarrow 5,\\ 45 &\rightarrow 5,\\ 67 &\rightarrow 7,\\ 35 &\rightarrow 5,\\ 22 &\rightarrow 2,\\ 82 &\rightarrow 2. \end{aligned} $$
이를 버킷 0~9에 순서대로 인큐하면
- 버킷 2: \(22, 82\)
- 버킷 5: \(25, 45, 35\)
- 버킷 6: \(86\)
- 버킷 7: \(67\)
- 버킷 8: \(48\)
그 다음
for(b = i = 0; b < BUCKETS; b++) while(!is_empty(b)) list[i++] = dequeue(b);
에 의해 버킷 0부터 9까지의 큐에서 차례로 디큐하여 배열에 다시 저장하면, 새 배열의 순서는
$$ 22,\ 82,\ 25,\ 45,\ 35,\ 86,\ 67,\ 48 $$
이 된다. 바로 이어지는
for(i = 0; i < cnt; i++) printf("%d ", list[i]);
에서 이 배열이 첫 번째 줄로 출력되므로, 첫 줄의 출력 결과는
$$ 22\ 82\ 25\ 45\ 35\ 86\ 67\ 48 $$
이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>