기수 정렬(Radix Sort) - 정의 / 예시 코드(C++)

 

기수 정렬(Radix Sort)은 비교 정렬 알고리즘이 아닌 정렬 알고리즘 중 하나로, 비교 대상의 특정한 속성을 이용하여 정렬하는 방법입니다. 기수 정렬은 숫자나 문자열과 같은 자료를 정렬하는 데에 주로 사용되며, 각 자릿수나 문자의 위치를 기준으로 정렬을 수행합니다.

 

기수 정렬의 동작 방식은 다음과 같습니다.

 

1. 가장 낮은 자릿수부터 시작하여 가장 높은 자릿수까지 반복적으로 정렬 작업을 수행합니다.

2. 각 자릿수를 기준으로 정렬하기 위해, 0부터 9까지의 버킷(또는 큐)을 생성합니다. 이 버킷은 해당 자릿수의 값을 가진 요소를 저장하는 용도로 사용됩니다.

3. 정렬할 자료를 순회하면서 각 요소의 해당 자릿수 값을 확인하고, 그에 맞는 버킷에 요소를 넣습니다. 예를 들어, 첫 번째 반복에서는 일의 자리 숫자를 확인하고 버킷에 요소를 넣습니다.

4. 버킷에 요소를 넣은 후, 버킷에 있는 요소들의 순서대로 꺼내서 원래 배열에 다시 저장합니다.

5. 가장 낮은 자릿수부터 가장 높은 자릿수까지 위의 과정을 반복합니다. 마지막 자릿수까지 정렬이 완료되면, 최종적으로 정렬된 배열이 얻어집니다.

 

반응형

기수 정렬은 안정적인 정렬 알고리즘이기 때문에 중복된 값이나 동일한 값을 가진 요소들도 올바른 순서로 정렬됩니다. 또한, 비교 연산을 사용하지 않고 자릿수를 기준으로 정렬하기 때문에 데이터의 크기에 상관없이 일정한 시간 복잡도를 가집니다. 그러나 기수 정렬은 정수나 문자열과 같은 자료의 자릿수가 고정되어 있어야 하고, 정렬하려는 자료의 크기가 큰 경우 메모리 사용량이 많아질 수 있습니다.

기수 정렬은 주로 정수나 문자열과 같은 자료를 정렬하는 데에 사용되며, 데이터의 특정 속성에 의해 정렬해야 할 때 유용합니다. 예를 들어, 학생들을 성적순으로 정렬하거나, 전화번호부를 알파벳순으로 정렬하는 데에 적용할 수 있습니다.

 

 

C++로 작성된 기수 정렬의 예시 코드입니다.

 

 

이 코드는 주어진 숫자 배열을 기수 정렬을 사용하여 정렬하고, 정렬된 결과를 출력합니다.