버킷 정렬 (Bucket Sort)
들어가는 말
버킷 정렬은 값의 범위별로 마련한 여러 버킷(bucket)에 원소를 나누어 담는다.
각 버킷에는 정해진 값의 범위에 속하는 원소가 모인다.
버킷 내부를 각각 정렬한 뒤 더 작은 값의 범위를 담당하는 버킷부터 원소를 꺼내면 오름차순 정렬이 완성된다.
버킷 정렬은 버킷의 개수가 적절하고 원소가 각 버킷에 고르게 분산될 때 효율적이다.
원소가 한 버킷에 지나치게 몰리면 전체 배열을 한 번에 정렬하는 것과 다르지 않다.
반대로 버킷이 너무 많아 원소가 듬성듬성 담기면 빈 버킷을 위한 메모리 사용량과 순회 비용이 늘어난다.
이 글에서는 0 이상 1 미만인 실수를 버킷 정렬로 오름차순 정렬하는 과정을 살펴본다.
정렬 과정 살펴보기
다음 15개의 원소를 오름차순으로 정렬해 보자.
0.78 0.17 0.39 0.26 0.72 0.94 0.21 0.12 0.23 0.68 0.05 0.33 0.51 0.84 0.66
1단계: 버킷에 원소 분배하기
버킷 정렬에서는 먼저 버킷의 개수와 각 버킷이 담당할 값의 범위를 정해야 한다.
버킷의 개수에 정해진 답은 없으며 입력값의 범위와 분포를 고려해 선택한다.
버킷이 너무 적으면 한 버킷에 많은 원소가 모여 내부 정렬 비용이 커지고, 너무 많으면 빈 버킷을 관리하는 비용이 늘어난다.
원소의 개수를 n, 버킷의 개수를 b라고 하자.
원소가 균등하게 분포한다고 가정하면 각 버킷에는 평균적으로 n / b개의 원소가 들어간다.
따라서 버킷 수를 원소 수에 비례하도록 정하면 각 버킷의 크기를 작게 유지할 수 있다.
다만 버킷 수와 원소 수가 같더라도 입력값이 특정 범위에 몰려 있으면 원소가 균등하게 나뉘지는 않는다.
원소 x가 들어갈 버킷의 인덱스는 로 계산한다.
버킷이 10개일 때 0.78은 7번 버킷에, 0.17은 1번 버킷에, 0.05는 0번 버킷에 들어간다.
다음 표에서 버킷이 10개일 때와 15개일 때 원소가 어떻게 분배되는지 비교해 보자.
| 버킷 인덱스 | 버킷이 10개일 때 | 버킷이 15개일 때 |
|---|---|---|
0 |
0.05 |
0.05 |
1 |
0.17 0.12 |
0.12 |
2 |
0.26 0.21 0.23 |
0.17 |
3 |
0.39 0.33 |
0.26 0.21 0.23 |
4 |
- | 0.33 |
5 |
0.51 |
0.39 |
6 |
0.68 0.66 |
- |
7 |
0.78 0.72 |
0.51 |
8 |
0.84 |
- |
9 |
0.94 |
0.66 |
10 |
0.72 0.68 |
|
11 |
0.78 |
|
12 |
0.84 |
|
13 |
- | |
14 |
0.94 |
버킷을 15개 사용하면 각 버킷이 담당하는 범위가 좁아져 원소가 더 세분화되어 분배된다.
다만 이 글에서는 원소가 들어갈 버킷을 쉽게 파악할 수 있도록 값의 범위를 0.1 간격으로 나눈 10개의 버킷을 사용하겠다.
2단계: 각 버킷 정렬하기
모든 값을 버킷에 분배한 뒤에는 각 버킷의 원소를 오름차순으로 정렬한다.
이때 각 버킷을 정렬하는 데 사용할 알고리즘은 구현자가 자유롭게 선택할 수 있다.
| 버킷 인덱스 | 정렬 전 | 정렬 후 |
|---|---|---|
0 |
0.05 |
0.05 |
1 |
0.17 0.12 |
0.12 0.17 |
2 |
0.26 0.21 0.23 |
0.21 0.23 0.26 |
3 |
0.39 0.33 |
0.33 0.39 |
4 |
- | - |
5 |
0.51 |
0.51 |
6 |
0.68 0.66 |
0.66 0.68 |
7 |
0.78 0.72 |
0.72 0.78 |
8 |
0.84 |
0.84 |
9 |
0.94 |
0.94 |
3단계: 버킷 합치기
각 버킷 내부는 정렬되어 있으며, 버킷 번호가 커질수록 더 큰 값이 들어 있다.
따라서 버킷 순서대로 원소를 꺼내 원래 배열에 저장하면 오름차순 정렬이 완성된다.
| 합치는 순서 | 배열에 추가하는 값 |
|---|---|
0 |
0.05 |
1 |
0.12 0.17 |
2 |
0.21 0.23 0.26 |
3 |
0.33 0.39 |
4 |
- |
5 |
0.51 |
6 |
0.66 0.68 |
7 |
0.72 0.78 |
8 |
0.84 |
9 |
0.94 |
시간 복잡도와 공간 복잡도
원소의 개수를 n, 버킷의 개수를 b라고 하자.
원소를 버킷에 분배하고 정렬된 버킷을 다시 합치는 데 각각 O(n)이 걸린다.
버킷 내부를 정렬하는 시간은 원소가 각 버킷에 어떻게 분포하는지에 따라 달라진다.
원소가 버킷에 고르게 분포하고 버킷 수가 원소 수에 비례하면 각 버킷에는 평균적으로 적은 수의 원소가 들어간다.
이 경우 모든 버킷을 정렬하는 데 걸리는 시간도 O(n)이므로 평균 시간 복잡도는 O(n)이다.
반면 모든 원소가 하나의 버킷에 몰리면 해당 버킷을 정렬하는 비용이 전체 성능을 좌우한다.
따라서 최악의 시간 복잡도는 버킷 내부에 사용하는 정렬 알고리즘에 따라 달라진다.
예를 들어 버킷 내부 정렬에 퀵 정렬을 사용하고 최악의 경우가 발생하면 전체 시간 복잡도는 O(n^2)이 된다.
버킷 b개를 만들고 관리하는 데 O(b)의 공간이 필요하다.
또한 원소 n개를 각 버킷에 나누어 담기 위해 O(n)의 공간이 필요하다.
따라서 전체 공간 복잡도는 O(n + b)이다.
소스 코드
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
void bucket_sort(double arr[], int size, int bucket_count)
{
vector<vector<double>> buckets(bucket_count);
for (int i = 0; i < size; i++)
{
int bucket_index = (int)(arr[i] * bucket_count);
buckets[bucket_index].push_back(arr[i]);
}
for (int i = 0; i < bucket_count; i++)
{
stable_sort(buckets[i].begin(), buckets[i].end());
}
int write_index = 0;
for (int i = 0; i < bucket_count; i++)
{
for (int j = 0; j < (int)buckets[i].size(); j++)
{
arr[write_index++] = buckets[i][j];
}
}
}
int main()
{
double arr[] = {
0.78, 0.17, 0.39, 0.26, 0.72,
0.94, 0.21, 0.12, 0.23, 0.68,
0.05, 0.33, 0.51, 0.84, 0.66
};
int size = sizeof(arr) / sizeof(arr[0]);
int bucket_count = 10;
bucket_sort(arr, size, bucket_count);
for (int i = 0; i < size; i++)
{
printf("%.2f ", arr[i]);
}
// Result: 0.05 0.12 0.17 0.21 0.23 0.26 0.33 0.39
// 0.51 0.66 0.68 0.72 0.78 0.84 0.94
return 0;
}구현 설명
C 언어로 작성하면 버킷 정렬의 동작을 구현하는 코드뿐만 아니라 버킷 자체를 구현하고 관리하는 코드도 필요하다.
버킷 수가 실행 중에 결정되는데 VLA를 사용할 수 없다면, bucket_count개의 버킷을 저장할 배열을 동적으로 할당해야 한다.
또한 각 버킷에 원소가 차례대로 삽입되도록 삽입 위치를 나타내는 인덱스를 관리하고, 저장 공간이 부족하면 배열을 확장해야 한다.
이러한 부가적인 코드를 줄이고 버킷 정렬의 동작에 집중할 수 있도록 C++로 작성했다.
다만 C++의 자료구조와 정렬 함수만 사용하고, 나머지는 배열과 인덱스 기반 반복문을 사용하는 C 스타일로 작성했다.
앞의 정렬 과정 살펴보기에서는 버킷 정렬의 과정을 세 단계로 나누어 살펴보았다.
bucket_sort 함수에서도 세 개의 바깥쪽 for 문이 각 단계와 순서대로 대응하도록 구성했다.
첫 번째 for 문은 입력 배열의 원소를 알맞은 버킷에 분배한다.
각 원소에 bucket_count를 곱한 값을 정수로 변환해 버킷 인덱스를 구하고, 해당 버킷에 원소를 추가한다.
두 번째 for 문은 stable_sort를 사용해 각 버킷의 원소를 오름차순으로 정렬한다.
세 번째 for 문은 버킷을 인덱스 순서대로 순회하며 정렬된 원소를 원본 배열에 차례대로 대입해 오름차순 정렬을 완성한다.