Radix Sort - 구름LEVEL
Radix Sort
Quiz Info
Quiz Info
Radix Sort
100points
Participant
21
Solved Rate
57.1%
0
0

Radix sort( 기수 정렬 )은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 자릿수가 고정되므로 안정적이고 O(dn)의 시간 복잡도를 가집니다(d : 가장 큰 데이터의 자리수).

비교 연산이 없으며, 속도도 매우 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다는 단점이 있습니다.

예를 들어서 Radix sort를 살펴보면,

50 20 319 218 3 99 라는 수열이 주어지면,


1) 1의 자리만 보고 정렬

50 20 3 218 319 99


2) 1)의 결과를 가지고 10의 자리에 대해 정렬

3 218 319 20 50 99


3) 2)의 결과를 가지고 100의 자리에 대해 정렬

3 20 50 99 218 319


이런 식으로 정렬이 완료 됩니다.

위 정렬 방법을 프로그램으로 작성하십시오.


입력

첫 줄에 수열의 개수

다음 줄에 공백으로 구분하여 수열 입력

출력

오름차순으로 정렬된 수열



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
6
5020319218399
Output
3205099218319
Example 2
Input
6
5143216
Output
1234651
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)