+) [JAVA] 기수정렬 알고리즘 정리 - radix sort

기수정렬(버킷정렬)

기수정렬( Radix Sort )이란,

숫자의 개별 자릿수를 기반으로 입력 데이터를 정렬하여 작동하는 정렬 알고리즘이다.

사용 중인 숫자 체계의 기본인 기수를 기준으로 숫자를 정렬하는데, 십진수에서의 기수는 10, 이진수에서의 기수는 2이다.

버킷정렬과 비슷하지만 차이점이 있다.

 

버킷정렬과 기수정렬 비교

정렬	기수정렬	버킷정렬
공통점	요소를 직접 비교하지 않는 정렬 알고리즘(non-comparative sorting algorithm)
요소 그룹화	개별 숫자 / 비트 기준. 낮은 자리부터 정렬 시작하여 높은자리까지 요소 정렬.	값의 범위를 동일한 크기의 간격(버킷)으로 나눠 해당 값을 버킷에 배포.
안정/불안정	안정. (동일한 요소의 상대적인 순서를 유지함)	불안정. 안정적이게 하기 위해 다른 알고리즘을 사용할 수 있지만, 이는 시간복잡도를 증가시킴.
시간복잡도	O(dn) (자세히 표시하자면, O(d(n+k)) 인데, 더해지는 실수 k는 곱해지는 수가 커짐에 따라 있으나마나이기 때문에 생략한다. 이때, d는 입력 값의 자릿수, n은 정렬되는 요소 수, k는 값의 범위이다.)	O(n) (자세히 표시하자면, O(n+k)이다.)

 

 

정렬 단계는 다음과 같다.

0~9까지의 버킷(큐,바구니)을 준비한다.

낮은 자리수부터 진행하는데, 이에 해당하는 버킷에 데이터를 넣는다.

0부터 차례대로 버킷에서 데이터를 꺼내온다.

낮은자리부터 가장 높은 자리수까지 이를 반복한다.

 

특징

비교 연산을 하지 않아 정렬 속도가 빠르지만,

데이터 전체 크기 + 기수 테이블의 크기 만큼의 메모리가 필요하다는 단점이 있다.

 

시간 복잡도는 O(dn)인데, 여기서 d는 최댓값의 자릿수이고, n은 입력 요소수 이다.

자릿수가 고정되어 있기에 안정된 정렬 방식이다.