가장 낮은 자릿수(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]
데이터307424132216241835546630
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]에 놓인다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 16년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기