[정보][자료구조] 2018-B-07 기수 정렬(Radix sort)

<작성 방법>

(1) 밑줄 친 ㉠ 명령문이 첫 번째 수행될 때와 두 번째 수행될 때 출력되는 내용을 각각 쓸 것.

Radix sort를 실행하는데, Q[2] -2로 정렬한 값을 각각 쓰면 된다.

127, 145, 870, 252, 325, 691, 471, 512

 

첫번째 : 252, 512

두번째 : 325, 127

 

(2) 밑줄 친 ㉡ 명령문이 첫 번째 수행될 때와 두 번째 수행될 때 출력되는 내용을 각각 쓸 것.

첫번째 : 870, 691, 471, 252, 512, 145, 325, 127

두번째 : 512, 325, 127, 145, 252, 870, 471, 691

 

(3) 위 알고리즘의 시간 복잡도를 빅-오(Big-oh) 표기법으로 쓸 것.

O(d(n+Q)) 라고 하는데, 이것은 어째 유도하는 방법을 알 수 가 없어 radix sort에 대해서는 암기를 하는 것이 좋을 것 같습니다.