TUTORIAL · Algorithm
버킷 정렬
이 자습서에서는 버킷 정렬 알고리즘을 소개합니다.
이 페이지의 내용
버킷 정렬은 비교 정렬이 아니라 분포 기반 정렬 알고리즘입니다. 값을 순서가 정해진 버킷에 분배하고, 각 버킷 안의 값을 정렬한 다음, 버킷을 순서대로 모아 결과를 만듭니다. 값이 알려진 범위에 비교적 고르게 분포할 때 특히 효과적입니다. 값에서 버킷으로 적절히 대응시키는 방법이 있다면 이 분배와 수집 방식이 유용합니다.
버킷 정렬 알고리즘
입력 범위를 덮도록 k개의 버킷을 정한 다음, 각 값을 해당 구간의 버킷에 대응시킵니다. [0, 1) 범위의 값에는 floor(k * x)라는 간단한 0부터 시작하는 규칙을 사용할 수 있습니다. 버킷 j는 [j/k, (j+1)/k) 구간을 담당합니다. 상한은 포함되지 않으므로 범위 안의 모든 값은 0부터 k - 1까지의 인덱스에 대응됩니다. 이 범위를 벗어나는 값에는 정규화나 다른 대응 규칙이 필요합니다. 이 공식이 모든 입력에 적용되는 것은 아닙니다.
절차는 다음과 같습니다.
- 선택한 범위에 맞춰
k개의 버킷을 만듭니다. - 입력값
x를 차례로 확인하고floor(k * x)번 버킷에 넣습니다. - 각 버킷을 따로 정렬합니다. 작은 버킷에는 삽입 정렬을 자주 사용하지만, 다른 내부 정렬 방법도 사용할 수 있습니다.
- 버킷을 인덱스 순서대로 살펴보며 정렬된 값을 결과에 추가합니다.
버킷 대응 규칙은 버킷 사이의 순서를 보존합니다. 버킷 j의 모든 값은 버킷 j + 1의 모든 값보다 작습니다. 각 버킷 안의 정렬은 같은 구간에 속한 값들의 순서를 정합니다. 위에서 연결한 삽입 정렬 문서에서는 간단한 내부 정렬 방법을 설명합니다. 아래 구현에서는 대신 C++ 표준 라이브러리의 sort 함수를 사용합니다.
버킷 정렬 예제
[0, 1) 범위를 열 개의 동일한 구간으로 나누면 인덱스는 floor(10 * x)가 됩니다. 구간은 [0.0, 0.1), [0.1, 0.2) 순서로 이어져 [0.9, 1.0)까지 계속됩니다. 특히 0.1은 왼쪽 끝값이 해당 구간에 포함되므로 버킷 1에 들어갑니다.
입력 (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31)을 분배하면 다음과 같습니다.
| 버킷 | 구간 | 내부 정렬 전 값 |
|---|---|---|
| 0 | [0.0, 0.1) |
— |
| 1 | [0.1, 0.2) |
0.1 |
| 2 | [0.2, 0.3) |
0.22, 0.21 |
| 3 | [0.3, 0.4) |
0.33, 0.38, 0.31 |
| 4 | [0.4, 0.5) |
0.45 |
| 5 | [0.5, 0.6) |
0.55 |
| 6–9 | [0.6, 1.0) |
— |
각 버킷을 정렬하면 버킷 2에는 0.21, 0.22가, 버킷 3에는 0.31, 0.33, 0.38이 들어갑니다. 값이 있는 나머지 버킷에는 각각 값 하나만 있습니다. 버킷 0부터 9까지 이어 붙이면 오름차순 결과 (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55)를 얻습니다.
버킷 정렬 알고리즘 구현
이 C++ 프로그램은 위에서 사용한 여덟 값을 그대로 사용합니다. 값을 열 개의 버킷에 분배하고 각 버킷을 정렬한 뒤, 모은 순서를 출력합니다. 출력에 표시되는 Sorted values: 레이블은 코드와 출력 블록의 원문을 그대로 유지하므로 영어로 표시됩니다.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
std::vector<double> bucketSort(const std::vector<double>& values,
std::size_t bucketCount) {
std::vector<std::vector<double>> buckets(bucketCount);
for (double value : values) {
const std::size_t index = static_cast<std::size_t>(value * bucketCount);
buckets[index].push_back(value);
}
std::vector<double> result;
result.reserve(values.size());
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
result.insert(result.end(), bucket.begin(), bucket.end());
}
return result;
}
int main() {
const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
0.38, 0.55, 0.21, 0.31};
const std::vector<double> sorted = bucketSort(values, 10);
std::cout << "Sorted values:";
for (double value : sorted) {
std::cout << ' ' << value;
}
std::cout << '\n';
return 0;
}
Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55
이 함수는 bucketCount가 양수이고 모든 값이 [0, 1) 범위에 있다고 가정합니다. 이 조건을 만족하면 계산된 인덱스가 버킷 벡터의 범위를 벗어나지 않습니다. 다른 범위의 값을 사용하려면 인덱스를 계산하기 전에 값을 정규화하거나 해당 범위에 맞는 대응 규칙을 정의하세요. 제공된 실행 증거에 따르면 이 프로그램은 종료 코드 0으로 실행을 마쳤으며, 위에 표시된 정렬 결과를 출력했습니다.
버킷 정렬 알고리즘의 복잡도
값의 개수를 n, 버킷 개수를 k, 버킷 j에 들어가는 값의 개수를 b_j라고 하겠습니다. 버킷을 만들고 값을 분배하는 데는 O(n + k) 시간이 걸립니다. 각 버킷에서 std::sort 같은 비교 정렬을 사용하면 추가 작업은 각 버킷의 정렬 비용 합인 O(Σ b_j log b_j)로 제한됩니다. 따라서 한 버킷에 값이 몰리면 전체 시간은 O(n log n)이 될 수 있습니다. 버킷 크기가 작게 유지되는 분포에서는 예상 실행 시간이 거의 선형에 가까워질 수 있습니다. 이때 흔히 k를 n에 비례하게 정하고 입력이 대략 균일하게 분포한다고 가정합니다. 알고리즘 이름만으로 이런 성능이 보장되지는 않습니다.
버킷 안에서 삽입 정렬을 사용하면 크기가 b_j인 버킷의 최악 시간은 O(b_j²)가 될 수 있습니다. 이 경우 한 버킷에 값이 몰리면 전체 실행 시간이 2차 시간이 될 수 있습니다. 성능을 추정할 때 내부 정렬 방법과 입력 분포를 함께 고려해야 하는 이유입니다.
보조 공간은 O(n + k)입니다. 버킷에 n개의 값이 저장되고 버킷 구조 자체에는 k개의 항목이 필요합니다. 이는 별도의 정렬된 벡터를 반환하는 이 구현이 사용하는 공간입니다. 각 값은 모든 버킷에 복사되지 않고 하나의 버킷에만 저장되므로 공간 복잡도는 O(n * k)가 아닙니다.