다음과 같은 7개의 십진수를 입력받아 3단계(three passes)의… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 7개의 십진수를 입력받아 3단계(three passes)의 기수 정렬(Radix Sort)을 수행하여 오름차순으로 정렬하려고 한다.379 - 508 - 706 - 193 - 984 - 155 - 133두 번째 단계를 수행한 후 부분 정렬되어진 결과는?
1
508 - 706 - 155 - 133 - 379 - 984 - 193
2
706 - 508 - 155 - 133 - 379 - 193 - 984
3
508 - 706 - 133 - 155 - 379 - 193 - 984
4
706 - 508 - 133 - 155 - 379 - 984 - 193
해설
일의 자리부터 정렬하는 기수 정렬에서 두 번째 단계 후 결과는 706 - 508 - 133 - 155 - 379 - 984 - 193이다.
1단계(일의 자리)는 자리값이 같으면 입력 순서를 유지해 193 - 133 - 984 - 155 - 706 - 508 - 379가 된다.
2단계(십의 자리)는 이 순서에서 십의 자리 0(706, 508), 3(133), 5(155), 7(379), 8(984), 9(193) 순으로 모으며, 같은 버킷 안에서는 안정성에 따라 앞 단계 순서가 유지된다.
- 508 - 706 - 155 - 133 - 379 - 984 - 193: 앞 단계 순서상 706이 508보다 앞서야 하고, 십의 자리 3인 133이 5인 155보다 앞서야 한다.
- 706 - 508 - 155 - 133 - 379 - 193 - 984: 133과 155의 순서가 뒤바뀌었고, 십의 자리 8인 984가 9인 193보다 뒤에 있다.
- 508 - 706 - 133 - 155 - 379 - 193 - 984: 십의 자리가 같은 706과 508의 앞 단계 순서가 깨졌고, 984와 193의 순서도 틀렸다.
오류나 개정된 내용이 보이면 알려주세요