버킷 정렬(Bucket Sort)은 데이터 항목들을 여러 개의 버킷에 나누어 담은 뒤, 각 버킷을 개별적으로 정렬하고, 마지막에 모든 요소를 다시 하나의 리스트로 모아 정렬된 결과를 얻는 기법입니다. 각 버킷에는 서로 비슷한 범위의 데이터가 담기며, 버킷 내부의 정렬에는 삽입 정렬이나 C++의 std::sort 같은 다른 정렬 알고리즘이 활용됩니다.
이 예제에서는 입력값이 0 이상 1 미만의 실수라고 가정합니다. 각 요소는 size * array[i]를 계산하여 버킷의 인덱스를 결정하므로, 값이 클수록 더 뒤쪽 버킷에 배치됩니다.
버킷 정렬 기법의 복잡도
시간 복잡도: 최선의 경우와 평균적인 경우 O(n + k), 최악의 경우 O(n²)
공간 복잡도: 최악의 경우 O(nk)
입력 − 정렬되지 않은 데이터 목록: 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
array[i]를 인덱스가 (size * array[i])인 버킷에 삽입한다
done
for i := 0 to size-1 do
bucket[i]를 정렬한다
done
for i := 0 to size-1 do
bucket[i]의 항목들을 차례대로 모아 array에 넣는다
done
End
예제 코드
다음은 C++로 작성한 버킷 정렬 프로그램입니다. 벡터(vector) 배열을 버킷으로 사용하고, 각 버킷을 STL의 sort 함수로 정렬한 뒤 원래 배열로 다시 옮기는 방식으로 동작합니다.
#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²)까지 저하될 수 있으므로, 데이터의 분포 특성을 고려하여 적용하는 것이 좋습니다.