[정렬] 특수 정렬 알고리즘(계수/기수/버킷)

• 계수 정렬, 기수 정렬, 버킷 정렬은 각각 특정한 상황에서 빛을 발하는 정렬 알고리즘
• 이들 알고리즘의 효율성은 데이터의 특성과 분포에 크게 의존함

 

계수 정렬 (Counting Sort)

특수한 사용 상황:

• 정수와 작은 범위:
  • 계수 정렬은 정수 데이터에 최적화. 특히 정수 값의 범위가 제한적일 때 매우 효율적
• 동일한 값의 빈번한 반복:
  • 동일한 값이 데이터셋 내에 빈번하게 반복되는 경우에도 계수 정렬이 유리
• 데이터의 범위가 작고, 데이터 양이 많은 경우:
  • 예를 들어, 점수나 나이와 같이 특정 범위 내에 있는 정수를 정렬할 때 유용

 

 

기수 정렬 (Radix Sort)

특수한 사용 상황:

• 긴 정수나 문자열 정렬:
  • 긴 정수나 문자열과 같은 데이터를 정렬할 때 기수 정렬은 효과적 (자릿수별로 정렬하기 때문)
• 비교 기반 정렬의 한계를 넘어서려는 경우:
  • 큰 데이터셋에서 비교 기반 정렬보다 빠를 수 있으며, 특히 데이터의 크기가 고르게 분포되어 있을 때 효율적\

 

 

버킷 정렬 (Bucket Sort)

특수한 사용 상황:

• 균일하게 분포된 데이터:
  • 데이터가 균일하게 분포되어 있고, 데이터셋의 범위가 알려져 있을 때 버킷 정렬은 매우 효율적
• 부동 소수점 숫자:
  • 버킷 정렬은 부동 소수점 숫자 같은 비정수 데이터에도 잘 작동. (데이터를 버킷에 할당하고 각 버킷을 개별적으로 정렬할 수 있기 때문)
• 추가 메모리 사용 가능:
  • 버킷 정렬은 추가적인 메모리 공간을 필요로 하며, 이를 효율적으로 사용할 수 있는 상황에서 적합

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」