버킷 정렬(Bucket Sort)은 데이터 항목들을 여러 개의 버킷(bucket)으로 분산시키는 정렬 기법입니다. 각 버킷에는 성격이 비슷한 데이터가 담기며, 분산이 완료되면 각 버킷을 다른 정렬 알고리즘(예: 삽입 정렬, 표준 라이브러리의 sort 함수 등)으로 개별적으로 정렬합니다. 마지막으로 모든 버킷의 요소를 순서대로 모아 원래 리스트에 합치면 정렬된 결과를 얻을 수 있습니다.
버킷 정렬은 특히 입력 데이터가 균등하게 분포되어 있을 때 뛰어난 성능을 보이며, 0과 1 사이의 실수처럼 값의 범위가 명확한 부동소수점 데이터를 정렬할 때 자주 활용됩니다.
버킷 정렬의 시간 및 공간 복잡도
시간 복잡도: 최선의 경우와 평균의 경우 O(n + k), 최악의 경우 O(n²)
공간 복잡도: 최악의 경우 O(nk)
여기서 n은 데이터의 개수, k는 버킷의 개수를 의미합니다. 데이터가 고르게 분포되어 있으면 각 버킷에 들어가는 요소 수가 적어져 전체 성능이 선형에 가깝게 향상되지만, 데이터가 특정 버킷에 몰릴 경우 최악의 성능이 나타날 수 있습니다.
입력과 출력 예시
입력:
정렬되지 않은 데이터 목록: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
정렬 전 배열: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
출력:
정렬 후 배열: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
알고리즘
bucketSort(array, size)
입력 − 데이터 배열과 배열 내 요소의 총 개수
출력 − 정렬된 배열
Begin
for i := 0 to size-1 do
insert array[i] into the bucket index (size * array[i])
done
for i := 0 to size-1 do
sort bucket[i]
done
for i := 0 to size -1 do
gather items of bucket[i] and put in array
done
End
알고리즘 단계 설명
분산(Distribute): 각 요소 array[i]를 인덱스 (size × array[i])에 해당하는 버킷에 삽입합니다.
정렬(Sort): 각 버킷을 개별적으로 정렬합니다.
수집(Gather): 버킷 번호가 낮은 것부터 차례대로 요소를 꺼내 원래 배열에 다시 채워 넣습니다.
C++ 구현 예제
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void display(float *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bucketSort(float *array, int size) {
vector<float> bucket[size];
for(int i = 0; i<size; i++) { //요소들을 서로 다른 버킷에 삽입
bucket[int(size*array[i])].push_back(array[i]);
}
for(int i = 0; i<size; i++) {
sort(bucket[i].begin(), bucket[i].end()); //각 벡터(버킷)를 개별 정렬
}
int index = 0;
for(int i = 0; i<size; i++) {
while(!bucket[i].empty()) {
array[index++] = *(bucket[i].begin());
bucket[i].erase(bucket[i].begin());
}
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
float arr[n]; //주어진 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bucketSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
실행 결과
Enter the number of elements: 10
Enter elements:
0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79
정리
버킷 정렬은 데이터를 버킷으로 나눈 뒤 각각 정렬하고 다시 합치는 방식으로 동작합니다. 데이터가 균등하게 분포되어 있다면 평균 O(n + k)의 매우 효율적인 성능을 기대할 수 있으며, 특히 실수형 데이터를 다룰 때 유용한 정렬 알고리즘입니다. 다만 데이터가 한쪽으로 치우쳐 있는 경우 성능이 크게 저하될 수 있다는 점을 유의해야 합니다.