काउंटिंग सॉर्ट एक स्थिर सॉर्टिंग तकनीक है, जिसका उपयोग छोटी संख्याओं की कुंजियों के अनुसार ऑब्जेक्ट्स को सॉर्ट करने के लिए किया जाता है। यह उन कुंजियों की संख्या गिनता है जिनके कुंजी मान समान हैं। यह सॉर्टिंग तकनीक तब कुशल होती है जब विभिन्न कुंजियों के बीच अंतर इतना बड़ा नहीं होता, अन्यथा यह स्पेस जटिलता बढ़ा सकती है।
काउंटिंग सॉर्ट तकनीक की जटिलता
समय जटिलता: O(n+r)
स्पेस जटिलता: O(n+r)
इनपुट - असॉर्टेड डेटा की एक सूची: 2 5 6 2 3 10 3 6 7 8
आउटपुट - सॉर्टिंग के बाद सरणी: 2 2 3 3 5 6 6 7 8 10
एल्गोरिदम
countingSort(array, size)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट: क्रमबद्ध सरणी
शुरुआत max = सरणी से अधिकतम तत्व प्राप्त करें। आकार [max+1] की काउंट सरणी परिभाषित करें i := 0 से max तक करें count[i] = 0 //काउंट सरणी में सभी तत्वों को 0 पर सेट करें हो गया i := 1 से size तक करें सरणी में मिली प्रत्येक संख्या की काउंट बढ़ाएं हो गया i := 1 से max तक करें count[i] = count[i] + count[i+1] //संचयी आवृत्ति ढूंढें हो गया i := size से 1 तक 1 से घटाकर करें आउटपुट सरणी में संख्या संग्रहीत करें count[i] घटाएं हो गया आउटपुट सरणी वापस करें अंत
उदाहरण कोड
#include<iostream> #include<algorithm> using namespace std; void display(int *array, int size) { for(int i = 1; i<=size; i++) cout << array[i] << " "; cout << endl; } int getMax(int array[], int size) { int max = array[1]; for(int i = 2; i<=size; i++) { if(array[i] > max) max = array[i]; } return max; //सरणी से अधिकतम तत्व } void countSort(int *array, int size) { int output[size+1]; int max = getMax(array, size); int count[max+1]; //काउंट सरणी बनाएं (max+1 संख्या में तत्व) for(int i = 0; i<=max; i++) count[i] = 0; //काउंट सरणी को सभी शून्य से आरंभ करें for(int i = 1; i <=size; i++) count[array[i]]++; //काउंट सरणी में संख्या काउंट बढ़ाएं। for(int i = 1; i<=max; i++) count[i] += count[i-1]; //संचयी आवृत्ति ढूंढें for(int i = size; i>=1; i--) { output[count[array[i]]] = array[i]; count[array[i]] -= 1; //समान संख्याओं के लिए काउंट घटाएं } for(int i = 1; i<=size; i++) { array[i] = output[i]; //आउटपुट सरणी को मुख्य सरणी में संग्रहीत करें } } int main() { int n; cout << "तत्वों की संख्या दर्ज करें: "; cin >> n; int arr[n+1]; //दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout << "तत्व दर्ज करें:" << endl; for(int i = 1; i<=n; i++) { cin >> arr[i]; } cout << "सॉर्टिंग से पहले सरणी: "; display(arr, n); countSort(arr, n); cout << "सॉर्टिंग के बाद सरणी: "; display(arr, n); }
आउटपुट
तत्वों की संख्या दर्ज करें: 10 तत्व दर्ज करें: 2 5 6 2 3 10 3 6 7 8 सॉर्टिंग से पहले सरणी: 2 5 6 2 3 10 3 6 7 8 सॉर्टिंग के बाद सरणी: 2 2 3 3 5 6 6 7 8 10