기수 정렬(radix sort) 설명

기수 정렬(radix sort)에 대해 알아보도록 하겠습니다. 

기수 별로 비교 없이 수행하는 정렬 알고리즘입니다. 

무슨 말인지 잘 모르시겠죠?? 아래의 예를 보시면 금방 이해하실 수 있으십니다. 

 

 

기수 정렬 예제

10진수로 예를 한번 들어보겠습니다. 

아래에 정렬이 되지 않은 수들을 기수 정렬을 통하여서 정렬을 해보도록 하겠습니다. 

4, 1, 5, 9, 11, 7, 12, 18, 0, 10, 23, 21, 2

 

위와 같은 수를 1의 자릿수를 기준으로 정렬을 진행합니다. 

0, 10, 1, 11, 21, 12, 2, 23, 4, 5, 7, 18, 9

 

다음으로 10의 자릿수를 기준으로 정렬을 진행합니다. 

0, 1, 2, 4, 5, 7, 9, 10, 11, 12, 18, 21, 23

 

이렇게 진행을 하면 깔끔하게 정렬이 되는 것을 확인할 수 있습니다. 이해가 잘 되셨나요???

 

 

기수 정렬의 장단점

기수 정령의 장점은 최적화를 진행할 경우에 굉장히 빠르게 진행이 될 수 있다는 것입니다.

연산 수도 굉장히 적어 보입니다.

 

반면에 단점은 자릿수가 커진다면 연산을 더 많이 진행을 해야 합니다.

위의 예는 10의 자리까지만 비교를 진행을 했으면 되었는데 만약에 100의 자리와 1000의 자리가 있을 경우에는 연산을 불필요하게 많이 할 수도 있습니다. 이것도 잘 이해가 안 되니 예시를 한번 들어보도록 하겠습니다. 

 

마찬가지로 10진수로 진행을 해보도록 하겠습니다. 

3634, 1092

 

1의 자리를 비교를 진행합니다. 

1092,  3634

 

10의 자리를 비교합니다. 

3634, 1092

 

100의 자리를 비교합니다. 

1092,  3634

 

마지막으로 1000의 자리를 비교합니다. 

1092,  3634

 

쓸데없이 많은 연산을 진행한 것을 볼 수 있습니다. 

 

위의 예처럼 만약 자릿수는 크고 정렬할 수들은 적을 경우 생각보다 많은 연산을 진행하게 됩니다. 

 

오늘은 기수 정렬이 무엇인지 간단하게 살펴보았습니다. 하시는 프로젝트에 도움이 되셨으면 좋겠네요.