버킷 정렬(Bucket Sort)

🟩 계수 정렬을 일반화한 것으로 간주 가능

특히 값의 범위가 골고루 퍼져있을 때 유용

 

EX) 0.0~1.0 사이의 소수점 수를 가진 큰 집합을 정렬

👉 숫자들이 골고루 분산되어 있다면 인덱스 지정이 어렵기 때문에 계수정렬은 적용이 어렵고, 버킷정렬이 유용

 

🟩 방법

1. 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든다.

2. 각 데이터를 해당하는 버킷에 넣고

3. 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후

4. 버킷 순서대로 각 데이터를 나열하는 정렬 방식

 

🟩 특징

안정 정렬 (중복된 값의 경우 입력 순서를 무작위로 뒤섞은 상태에서 정렬하는 것)

제자리 정렬 알고리즘 X

 

🟩 시간복잡도 O(n)

하지만 한 버킷에 입력 키값들이 몰린 경우에는 버킷에 속하는 키들을 정렬하는데 사용한 정렬의 시간복잡도 보다 오랜 실행시간이 소요된다. 그렇기 때문에 최악의 경우는 한 버킷에 키 값들이 몰린 경우이며, 최상의 경우는 각 버킷에 입력 키값들이 균등하게 분배된 경우이다.