काउंटिंग सॉर्ट

गणना छँटाई एक स्थिर छँटाई तकनीक है, जिसका उपयोग वस्तुओं को छोटी संख्याओं की कुंजियों के अनुसार क्रमबद्ध करने के लिए किया जाता है। यह उन कुंजियों की संख्या की गणना करता है जिनके प्रमुख मान समान हैं। यह छँटाई तकनीक तब प्रभावी होती है जब विभिन्न कुंजियों के बीच का अंतर इतना बड़ा न हो, अन्यथा, यह स्थान की जटिलता को बढ़ा सकता है।

सॉर्ट तकनीक गिनने की जटिलता

• समय जटिलता:O(n+r)
• अंतरिक्ष जटिलता:O(n+r)

इनपुट और आउटपुट

इनपुट:क्रमबद्ध डेटा की एक सूची: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 
एल्गोरिदम
 <पूर्व>गणना क्रम(सरणी, आकार)

इनपुट :डेटा की एक सरणी, और सरणी में कुल संख्या

आउटपुट :क्रमबद्ध सरणी

अधिकतम प्रारंभ करें =सरणी से अधिकतम तत्व प्राप्त करें। आकार की गणना सरणी को परिभाषित करें [अधिकतम + 1] i के लिए:=0 से अधिकतम गिनती करें [i] =0 i के लिए किए गए सरणी में पाया गया है:=1 से अधिकतम गिनती [i] =गिनती [i] + गिनती [i + 1] आउटपुट ऐरे में कमी की संख्या [i] किया गया आउटपुट ऐरे को वापस करेंअंत

उदाहरण

#शामिल करें <""; cout < max) max =array[i]; } वापसी अधिकतम; // सरणी से अधिकतम तत्व} शून्य गिनती (इंट * सरणी, इंट आकार) {इंट आउटपुट [आकार + 1]; इंट मैक्स =गेटमैक्स (सरणी, आकार); इंट गिनती [अधिकतम + 1]; // गिनती सरणी बनाएं (अधिकतम + 1 तत्वों की संख्या) के लिए (int i =0; i<=max; i++) गिनती [i] =0; // गिनती सरणी को सभी शून्य के लिए प्रारंभ करें (int i =1; i <=आकार; i ++) गिनती [सरणी [i]] ++; // काउंट ऐरे में नंबर काउंट बढ़ाएँ। for(int i =1; i<=max; i++) count[i] +=count[i-1]; // के लिए संचयी आवृत्ति खोजें (int i =size; i>=1; i--) {आउटपुट [गिनती [सरणी [i]]] =सरणी [i]; गिनती [सरणी [i]] - =1; // समान संख्याओं के लिए गिनती घटाएं} के लिए (int i =1; i <=आकार; i ++) {सरणी [i] =आउटपुट [i]; // स्टोर आउटपुट ऐरे को मेन ऐरे में}}इंट मेन () {इंट एन; cout <<"तत्वों की संख्या दर्ज करें:"; सिनेमा>> एन; इंट एआर [एन+1]; // दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout <<"तत्व दर्ज करें:" <> arr[i]; } cout <<"छँटाई से पहले सरणी:"; प्रदर्शन (गिरफ्तारी, एन); गिनती सॉर्ट (गिरफ्तारी, एन); cout <<"सॉर्ट करने के बाद सरणी:"; प्रदर्शन (गिरफ्तारी, एन);}

आउटपुट

तत्वों की संख्या दर्ज करें: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