버킷 정렬(Bucket Sort) 의 개념
버킷 정렬은 데이터를 여러 개의 버킷으로 나누고, 각 버킷을 개별적으로 정렬한 후 병합해 전체 데이터를 정렬하는 방식입니다.
- 버킷을 생성하고,
- 입력 데이터를 버킷에 분배한 다음
- 각 버킷을 개별적으로 정렬하고,
- 각 버킷들을 합쳐 최종적인 정렬 결과를 생성하게 됩니다.
버킷 정렬의 Python 구현
Python 으로 버킷 정렬을 아래와 같이 구현할 수 있습니다.
def bucket_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
# 입력 배열에서 최댓값과 최솟값 찾기
min_val, max_val = min(arr), max(arr)
# 버킷의 수와 간격 계산
bucket_range = max_val - min_val
bucket_count = len(arr)
interval = bucket_range / bucket_count
# 버킷 생성
buckets = [[] for _ in range(bucket_count)]
# 입력 데이터를 버킷에 분배
for num in arr:
index = int((num - min_val) / interval)
index = min(index, bucket_count - 1) # 최댓값이 마지막 버킷에 들어가도록 보장
buckets[index].append(num)
# 각 버킷을 개별적으로 정렬
for bucket in buckets:
insertion_sort(bucket)
# 버킷을 합쳐 최종 정렬 결과 생성
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(bucket)
return sorted_arr
위의 버킷 정렬 구현은 아래와 같이 동작합니다.
arr = [85, 68, 65, 100, 88, 60, 82, 95]
알고리즘에서는 먼저 입력값의 범위를 계산한 다음, 입력값의 범위를 균등하게 분배해 각 버킷의 구간의 크기를 계산합니다. 위의 배열에서 최솟값은 60, 최댓값은 100입니다. 버킷 정렬은 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만드는데, 값을 균등하게 나누려면 배열의 최댓값에서 최솟값을 뺀 다음, 배열의 크기대로 나눠주면 됩니다. 이 경우, (100-60/8) 이 되어 구간 크기는 5가 됩니다.
마지막
arr = [85, 68, 65, 100, 88, 60, 82, 95]
# 배열의 크기만큼 버킷 생성
# 60~64 / 65~69 / 70~74 / 75~79 / 80~84 / 85~89 / 90~94 / 95~100
[[ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]]
그리고, 알고리즘은 각 값을 버킷에 분배합니다.
arr = [85, 68, 65, 100, 88, 60, 82, 95]
# 버킷 분배
# 60~64 / 65~69 / 70~74 / 75~79 / 80~84 / 85~89 / 90~94 / 95~100
[[60], [68, 65], [], [], [82], [85, 88], [], [100, 95]]그리고, 각 버킷별로 삽입 정렬을 수행해 버킷의 값을 정렬시킵니다.
# 버킷 분배
# 60~64 / 65~69 / 70~74 / 75~79 / 80~84 / 85~89 / 90~94 / 95~100
[[60], [68, 65], [], [], [82], [85, 88], [], [100, 95]]
# 각 버킷에 대해 삽입 정렬 수행
[[60], [65, 68], [], [], [82], [85, 88], [], [95, 100]]이제 버킷을 모두 합쳐 최종 결과를 생성합니다.
# 각 버킷에 대해 삽입 정렬 수행
[[60], [65, 68], [], [], [82], [85, 88], [], [95, 100]]
# 각 버킷의 값을 모두 합침
[60, 65, 68, 82, 85, 88, 95, 100]
버킷 정렬의 성능 분석과 특징
- 버킷 정렬의 시간 복잡도는
O(n)입니다. - 버킷 정렬은 버킷의 개수가 입력 데이터의 개수에 비례해야 유용합니다.
- 버킷의 개수가 상수 개로 정해져 있다면, 각 버킷에 들어가는 개수는 입력 데이터의 개수에 비례하게 됩니다. 그리고 그 비례하는 데이터에 대해서 모두 삽입 정렬을 수행하게 되죠. 그것은 버킷의 개수가 상수 개라면, 버킷 정렬은 선형 시간에 동작하지 못할 것이라는 의미입니다.
- 버킷의 개수가
n/k(k는 상수) 개라면, 버킷에는 상수 개의 데이터가 들어가게 되고 각 버킷은 데이터의 크기에 상관없이 상수 시간에 정렬할 수 있게 됩니다.
- 버킷 정렬은 안정적인 정렬 알고리즘입니다.
- 버킷 정렬은 제자리 정렬 알고리즘입니다.