버킷 정렬 기술에서 데이터 항목은 버킷 세트로 분산됩니다. 각 버킷은 유사한 유형의 데이터를 보유할 수 있습니다. 배포 후 각 버킷은 다른 정렬 알고리즘을 사용하여 정렬됩니다. 이후 모든 요소를 메인 리스트에 모아서 정렬된 형태를 얻습니다.
버킷 정렬 기법의 복잡성
-
시간 복잡도:최상의 경우와 평균적인 경우는 O(n + k), 최악의 경우는 O(n^2)입니다.
-
공간 복잡도:최악의 경우 O(nk)
입력 및 출력
Input: A list of unsorted data: 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 Output: Array after Sorting: 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
예시
#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++) { //put elements into different buckets
bucket[int(size*array[i])].push_back(array[i]);
}
for(int i = 0; i<size; i++) {
sort(bucket[i].begin(), bucket[i].end()); //sort individual vectors
}
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]; //create an array with given number of elements
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