[CLRS] [8-3] Bucket Sort(버킷 정렬)

1. Bucket Sort?

- Bucket Sort는 데이터를 일정한 범위로 나눈 여러 버킷에 분배하고,

- 각 버킷 내부에서 정려한 후 각 버킷을 합쳐서 전체 데이터를 정렬하는 알고리즘이다.

- 마치 다음 그림과 같다.

 

- 그림을 보면 알 수 있겠지만,

- 데이터가 특정 범위 안에서 균등하게 분포된 경우 매우 효율적으로 작동한다.

- 주로 0과 1사이의 실수나 버뮈가 제한된 정수를 정렬할 때 사용된다.

 

2. Bucket Sort의 알고리즘

i) 버킷 분할:

- 데이터를 특정 구간으로 나누어 각 구간을 '버킷'이라고 정의한다.

- 이때 버킷의 개수는 데이터의 분포에 따라 적절히 설정하는 것이 중요하다.

 

ex) 데이터가 0과 1사이의 실수라면 각 버킷은

[0,0.1) , [0.1,0.2), ... , [0.9,1)로 설정 가능

 

ii) 데이터 분배

- 주어진 데이터를 순회하면서 각 데이터가 속할 버킷을 결정한다.

ex)

- 데이터 값이 0.35라면 [0.3, 0.4) 버킷에 할당한다.

 

iii) 버킷 내부 정렬:

- 각 버킷 내에서 정렬 알고리즘을 사용하여 정렬을 수행한다.

- 이때 사용하는 정렬은 어떤걸 사용해도 무관하나, 해당 게시글에선 파이썬 내장 sort를 사용할 예정이다.

 

iv) 버킷 병합:

- 머든 버킷이 정렬되면, 버킷을 차례대로 연결하여 최종 정렬된 배열을 얻는다.

 

3. Bucket Sort의 시간복잡도

- Bucket Sort의 시간복잡도는 O(n+k)와 같다.

n : 데이터 개수

k : 버킷의 개수

 

4. Code 구현

def bucket_sort(arr):
    #1. 빈 버킷 생성
    num_buckets = 10
    buckets = [[] for _ in range(num_buckets)]

    #2. 각 요소를 적절한 버킷에 넣음
    for value in arr:
        index = int(value * num_buckets)
        buckets[index].append(value)

    #3 각 버킷 내부에 정렬
    for i in range(num_buckets):
        buckets[i].sort()

    #4 버킷 병합
    result_arr = []
    for bucket in buckets:
        result_arr.extend(bucket)

    return result_arr