기수 정렬(Radix Sort)

기수 정렬이라 함은??

정렬할 Item이 숫자인 경우에만 가능한 정렬 방식으로, 숫자의 자리 수를 이용하여 크기 비교하는 정렬.

그림과 함께 보자.

1. 위의 그림과 같이 [32, 87, 20, 92, 57] 로 나열되어 있는 배열을 기수 정렬을 하려고 한다.

우선 일의 자리수에 대해서만 비교하도록 한다. 각 배열 값의 일의 자리 수에 해당되는 값을 큐에 집어 넣는다.

32 같은 경우엔 일의 자리가 2이므로 2 index를 가진 큐에 집어넣고 나머지도 같은 방식으로 큐에 집어넣은다.

큐에 다 집어 넣으면, 0 index 부터 차례대로 다시 가져온다.

가져온 결과 값이 [20, 92, 32, 57, 87] 이며, 이 값은 일의 자리에 대한 sorting 결과 이다.

2. 십의 자리 수에 대해 다시 기수 정렬을 한다. 방식은 일의 자리 수 정렬과 동일하며, 

해당 큐에는 위의 그림과 같이 쌓이게 된다.

큐에 아이템이 다 쌓였으면, 순차적으로 가져온다.

결과적으로 [20, 32, 57, 87, 92] 이렇게 정렬이 완료 된다.