35. Radix Sort

기수 정렬(Radix Sort)은 자릿수가 있는 데이터를 정렬할 수 있는 방법으로, 가장 낮은 자리부터 시작해서 각각의 자리값을 기준으로 한 번씩 정렬을 실행한다. 이 과정이 끝나면 전체 데이터를 정렬할 수 있게 된다.

 

다음과 같은 데이터가 있을 때,

 

[811, 310, 659, 156, 27, 230, 384, 905, 422, 513, 324]

 

기수 정렬을 이용해 이 값들을 오름차순으로 정렬한다고 하면 다음과 같은 과정을 거치게 된다. 먼저 일의 자리를 기준으로 값들을 분류한다.

 

[811]

[310, 230]

[659]

[156]

[27]

[384, 324]

[905]

[422]

[513]

 

이 값들을 일의 자리 수가 작은 순서대로 모두 이어붙인다.

 

[310, 230, 811, 422, 513, 384, 324, 905, 156, 27, 659]

 

다음으로 이 값들을 십의 자리를 기준으로 분류한다. 이때 같은 묶음 내에서 원소의 상대적인 순서가 유지되어야 한다.

 

[310, 811, 513]

[230]

[422, 324, 27]

[384]

[905]

[156, 659]

 

이 값들을 십의 자리 수가 작은 순서대로 모두 이어붙인다.

 

[905, 310, 811, 513, 422, 324, 27, 230, 156, 659, 384]

 

다음으로 이 값들을 백의 자리를 기준으로 분류한다.

 

[905]

[310, 324, 384]

[811]

[513]

[422]

[27]

[230]

[156]

[659]

 

이 값들을 백의 자리 수가 작은 순서대로 모두 이어붙인다.

 

[27, 156, 230, 310, 324, 384, 422, 513, 659, 811, 905]

 

천의 자리 이상은 모두 $0$이므로 정렬이 완료되었다. 여기서는 십진법을 기준으로 자리수를 정했지만 다른 기수법을 사용해서 정렬할 수도 있다.

 

다음은 기수 정렬 과정을 시각화한 것이다.

데이터의 최대 자리수가 $k$일 때 기수 정렬의 시간복잡도는 $\Theta(kn)$이며 $k$를 상수로 취급하면 $\Theta(n)$의 시간복잡도가 나오게 된다. 하지만 메모리 사용량이 많고, 문자열이나 실수를 정렬할 때는 성능이 떨어진다는 단점이 존재한다.

 

→ solved.ac tag: sorting