가장 낮은 자릿수(LSD : Least Significant Digit… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
가장 낮은 자릿수(LSD : Least Significant Digit) 우선 방식의 기수 정렬(radix sort)을 이용하여, 다음과 같이 배열에 저장된 10진수 데이터를 오름차순으로 정렬하고자 한다. 오른쪽에서 두 번째 자릿수(digit) 기준의 정렬 단계 후에 위치 [3]에 있는 데이터로 옳은 것은? (단, 각 단계별 정렬의 기준이 되는 자릿수는 0에서 9까지의 값을 가진다)
| 위치 | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] |
|---|---|---|---|---|---|---|---|---|
| 데이터 | 307 | 424 | 132 | 216 | 241 | 835 | 546 | 630 |
1
630
2
546
3
132
4
216
해설
두 번째 자릿수 정렬 후 위치 [3]에는 630이 온다.
LSD 기수 정렬은 일의 자리부터 자릿수별로 안정 정렬을 반복하므로, 같은 자릿값끼리는 이전 단계의 순서를 유지한다.
일의 자리 정렬: 630, 241, 132, 424, 835, 216, 546, 307
십의 자리 정렬: 307, 216, 424, 630, 132, 835, 241, 546
십의 자리가 3인 630, 132, 835 중 앞 단계에서 먼저 있던 630이 위치 [3]에 놓인다.
- 546은 십의 자리 정렬 후 맨 마지막 위치 [7]에 있다.
- 132는 십의 자리가 630과 같지만 일의 자리 단계에서 630 뒤에 있었으므로 위치 [4]에 놓인다.
- 216은 십의 자리가 1이라 위치 [1]에 놓인다.
오류나 개정된 내용이 보이면 알려주세요