그림으로 알아보는 기수 정렬 (radix sort)

기수 정렬

각 자리수에 대해 정렬하여 전체의 정렬결과를 얻어오는 정렬방식. 

정렬할 요소가 정수인 경우에만 사용할 수 있다.

각 기수에 대하여 정렬하는 과정은 보통 큐를 이용하여 구현한다.

배열을 순차적으로 탐색하면서 알맞은 큐에 집어넣고,

모든 요소를 다 집어넣었으면 

작은 큐부터 순서대로 빼낸다.

기수정렬을 내림차순으로 하고싶은 경우에는,

큰 큐부터 꺼내면 된다.

시간 복잡도

각 기수에 대하여 같은 작업을 반복하기 때문에,

MAX 값의 자리수가 크면 클수록 소요되는 시간이 증가한다.

STEP의 개수 : 최대값의 기수 값. (d)

순차적으로 큐에 넣는 작업 : 배열의 사이즈. (n)

즉, 시간 복잡도는 O(d*n).

d는 가장 큰 수의 자리수 값.

코드