बकेट सॉर्टिंग तकनीक में, डेटा आइटम बकेट के एक सेट में वितरित किए जाते हैं। प्रत्येक बकेट में समान प्रकार का डेटा हो सकता है। वितरण के बाद, प्रत्येक बाल्टी को दूसरे सॉर्टिंग एल्गोरिदम का उपयोग करके सॉर्ट किया जाता है। उसके बाद सॉर्ट किए गए फॉर्म को प्राप्त करने के लिए सभी तत्वों को मुख्य सूची में इकट्ठा किया जाता है।
बकेट सॉर्ट तकनीक की जटिलता
-
समय जटिलता:सर्वोत्तम मामले के लिए ओ (एन + के) और सबसे खराब मामले के लिए औसत मामले और ओ (एन 2)।
-
अंतरिक्ष जटिलता:ओ (एनके) सबसे खराब स्थिति के लिए
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 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(सरणी, आकार)
इनपुट :डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट :क्रमबद्ध सरणी
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