다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

다음은 기수정렬 알고리즘이다. ㉠이 두 번 실행된 후의 결과로 옳은 것은?
<조 건>
○ 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

두 번째 출력은 7 125 632 437 85 194이다. LSD 기수 정렬은 일의 자리, 십의 자리 순으로 버킷에 나누었다가 같은 버킷 안의 순서를 유지하며 다시 모은다.
1회차(일의 자리): 632(2), 194(4), 125·85(5), 437·7(7)
→ 632 194 125 85 437 7
2회차(십의 자리): 7(0), 125(2), 632·437(3), 85(8), 194(9)
→ 7 125 632 437 85 194
632 194 125 85 437 7은 일의 자리만 처리한 첫 번째 출력이다.
7 85 125 194 437 632는 백의 자리까지 마친 세 번째(최종) 출력이다.
632 194 125 437 85 7은 어느 단계의 출력과도 일치하지 않는다.