[알고리즘] 기수 정렬 (Radix Sort) & 계수 정렬 (Counting Sort)

기수 정렬 (Radix Sort)

• 낮은 자릿수부터 정렬하는 방식
• 시간 복잡도 : O(dn) → d: 최대 자릿수
• 장점
  • 각 원소 간의 비교 연산을 하지 않아 빠르다.
  • 문자열, 정수 정렬 가능
    
    
• 단점
  • 자릿수가 없는 것은 정렬할 수 없다. (ex. 부동 소숫점)
  • 기수 테이블을 위한 메모리가 필요하다.

계수 정렬 (Counting Sort)

• 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리 필요
• 시간 복잡도 : O(n + k) → k: 정렬 대상 데이터 중 최댓값