[알고리즘] 버킷 정렬

[Bucket Sort (버킷 정렬)]

버킷 정렬은 N개의 버킷으로 나눈 뒤, 각 버킷 안에 하나 이상의 값을 저장한다. 예를 들어보어 사과(2개), 배(2개), 망고(3개), 수박(1개) 총 8개의 과일이 있다고 가정해보자. 버킷 정렬에서는 다음과 같이 과일의 정보를 저장한다.

버킷 정렬 도식도

 

숫자 범위를 기준으로 버킷의 정렬 순서를 정할 수도 있다. 예를 들어 29, 25, 3, 49, 9, 37, 21, 43 이라는 숫자가 있으면 이를 10단위로 나누어 관리할 수 있다.

출처 : 위키피디아

 

[구현]

두 번째 예시를 기준으로 의사 코드를 작성하면 다음과 같다. 

function bucketSort(array, k) 
    buckets ← N 크기의 빈 배열을 선언한다.
    M ← 가장 큰 숫자를 M으로 선언한다. 
    for i = 1 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 1 to k do
        nextSort(buckets[i])
    return the concatenation of buckets[1], ...., buckets[k]

[시간 복잡도]

가까운 값을 가진 값을 가진 키가 여럿일 경우 이 키들은 같은 버킷에 들어갈 확률이 높아 어떤 버킷은 다른 버킷보다 더 많은 원소를 가질 수 있다. 최악의 경우에는 모든 원소가 하나의 버킷에 들어갈 수 있다. 이 경우 O(n^2)이 된다. 

하지만 입력이 균등하게 분포한다면 평균 시간 복잡도는 O(n)이 된다. 즉, 버킷 정렬은 주로 입력이 일정 범위에 걸쳐 균등 분포에 가까울 때 유용하다.

 

[관련 알고리즘 문제]

https://leetcode.com/problems/top-k-frequent-elements/