기수 정렬

기수 정렬의 핵심 이론

기수 정렬(radix sort)은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.

 

수행 방식

기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.