[자료구조] 기수정렬

기수정렬이란?

낮은 자리수부터 비교하여 차례대로 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘

 

1. 자릿수 배열(자릿수에 대한 값의 배열을 담음) 누적으로 값을구함
2. 원소값 뒤에서부터 결과 배열에 자릿수를 기준으로 정렬을 함(1의자리까지 정렬)
3. 10의자리를 기준으로 자릿수 누적값 구함
4. 원소로 만듦

• 각 데이터의 자릿수를 기준으로 분류하므로 가장큰 자릿수를 D라고 했을때 O(DN)의 시간 복잡도를 가짐(1의 자리, 10의 자리...)
• 실제로 D는 그렇게 큰 값이 아니게 형성이되어 O(N)에 가까운 시간 복잡도를 가지므로 제법 빠른 알고리즘
• 계수정렬보다는 약간 느리지만 숫자가 큰 상황에서도 사용가능
• 부동소수점 실수 등에는 사용할 수 없음

 

이미치 출처 : https://www.ritambhara.in/radix-sort/

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수