다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것은?
<조 건> | ||
○ LSD(Least Significant Digit)는 가장 낮은 자릿수이고, MSD(Most Significant Digit)는 가장 높은 자릿수이다. 135의 경우 LSD 위치의 값은 5이고 MSD 위치의 값은 1이다.
○ 버킷은 10개 큐로 구현한다.
○ list는 배열로 구현하며 초깃값은 (437, 125, 85, 7, 632, 194)이고 n은 6이다. | ||
RadixSort(list, n) {
for(d ← LSD의 위치에서 MSD위치로 한 자리씩 이동){
for(i ← list의 0번째 원소부터 n-1까지 반복){
list의 i번째 원소를 d의 위칫값에 따라 0번부터 9번 사이의 버킷에 삽입한다.
}
for(b ← 0번 버킷부터 9번 버킷까지 반복){
b번째 버킷에서 원소들을 순차적으로 읽어서 list에 재배정한다.
}
㉠ list의 원소를 순서대로 출력한다.
}
} | ||
- ①7 85 125 194 437 632
- ②7 125 632 437 85 194
- ③632 194 125 85 437 7
- ④632 194 125 437 85 7
선지를 골라 바로 채점해 보세요.
정답 ②
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)