기수정렬이란? 기수정렬은 영어로 'Radix Sort' 이다. 여기에서 'Radix'가 의미하는 바는 각 자리를 이루고 있는 숫자들을 말한다. 즉, 각각의 수의 자릿수를 대상으로 정렬한다는 것이다. 기수정렬을 다른 정렬들(버블정렬, 퀵정렬 등) 과는 다른 특성이 있다. 첫 번째는 비교가 이루어지지 않는 정렬이라는 것이고, 두 번째는 정렬의 이론상 한계인 O(N * log N)을 뛰어넘는 O(N)이라는 것이다. 이렇게만 보면 어떤 정렬보다 좋을 것 같지만 실제로는 생각보다 많이 쓰이지않는데, 이는 적용 범위가 한정적이기 때문이다. 반대로 말하면, 최적의 상황에서 사용하면 최적의 효율을 보여준다는 것이기도 하다. (실제로, 알고리즘 풀이 중에서는 쓰이는 경우가 간간히 있다.) 동작 원리 다음과 같은 배열을 ..