요약
- 분배 정렬의 일종으로 데이터가 균등 분포일 때 O(N+K) 시간 복잡도
본문
분배 정렬의 일종으로 데이터를 여러개의 버킷으로 분할 한 후 각 버킷 내에서 독립적으로 정렬하는 방식. 데이터가 균등하게 분포되어 있을때 효과적
- 주어진 데이터를 일정 범위를 가진 여러 버킷으로 분배
- 각 버킷내의 데이터를 개별적으로 정렬
- 모든 버킷의 정렬된 데이터를 순서대로 합침
시간 복잡도: O(N+K), 최악의 경우 O(N^2) 공간 복잡도: O(N+K)
예시
0~99의 숫자가 랜덤하게 배열되어 있는 리스트를 정렬한다고 가정
- 각 버킷은 0-9, 10-19, 20-29, … , 90-99의 범위를 담당
- 데이터 분배: [29, 25, 3, 49, 9, 37, 21, 43]
- 0-9 버킷: [3, 9]
- 10-19 버킷: []
- 20-29 버킷: [29, 25, 21]
- 30-39 버킷: [37]
- 40-49 버킷: [49, 43]
- 나머지 버킷: []
- 각 버킷 정렬 (예: 삽입 정렬):
- 0-9 버킷: [3, 9]
- 20-29 버킷: [21, 25, 29]
- 30-39 버킷: [37]
- 40-49 버킷: [43, 49]
- 결과 병합: [3, 9, 21, 25, 29, 37, 43, 49]