बकेट सॉर्टिंग तकनीक में, डेटा आइटम्स को बकेट के एक सेट में वितरित किया जाता है। प्रत्येक बकेट समान प्रकार के डेटा को रख सकता है। वितरित करने के बाद, प्रत्येक बकेट को दूसरे सॉर्टिंग एल्गोरिदम का उपयोग करके सॉर्ट किया जाता है। उसके बाद सभी तत्वों को मुख्य सूची में इकट्ठा किया जाता है ताकि क्रमबद्ध रूप प्राप्त हो सके।
बकेट सॉर्ट तकनीक की जटिलता
समय जटिलता: सर्वोत्तम और औसत मामले के लिए O(n + k) और सबसे खराब स्थिति के लिए O(n2)।
स्पेस जटिलता: सबसे खराब स्थिति के लिए 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)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट: क्रमबद्ध सरणी
शुरुआत i := 0 से size-1 तक करें सरणी[i] को बकेट इंडेक्स (size * सरणी[i]) में डालें हो गया i := 0 से size-1 तक करें बकेट[i] को सॉर्ट करें हो गया i := 0 से size -1 तक करें बकेट[i] के आइटम इकट्ठा करें और सरणी में डालें हो गया अंत
उदाहरण कोड
#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 << "तत्वों की संख्या दर्ज करें: "; cin >> n; float arr[n]; //दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout << "तत्व दर्ज करें:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "सॉर्टिंग से पहले सरणी: "; display(arr, n); bucketSort(arr, n); cout << "सॉर्टिंग के बाद सरणी: "; display(arr, n); }
आउटपुट
तत्वों की संख्या दर्ज करें: 10 तत्व दर्ज करें: 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
