डेटा संरचनाओं में छँटाई विधियों की तुलना

यहां हम कुछ छँटाई के तरीके देखेंगे। 200+ छँटाई तकनीकें हैं। हम उनमें से कुछ को देखेंगे। कुछ छँटाई तकनीक तुलना आधारित छँटाई हैं, कुछ गैर-तुलना आधारित छँटाई तकनीक हैं।

तुलना आधारित सोरिंग तकनीकें बबल सॉर्ट, सिलेक्शन सॉर्ट, इंसर्शन सॉर्ट, मर्ज सॉर्ट, क्विकसॉर्ट, हीप सॉर्ट आदि हैं। इन तकनीकों को तुलना आधारित सॉर्ट माना जाता है क्योंकि इन तकनीकों में मूल्यों की तुलना की जाती है, और अलग-अलग चरणों में क्रमबद्ध स्थिति में रखा जाता है। यहां हम इन तकनीकों की समय जटिलता देखेंगे।

विश्लेषण प्रकार	बबल सॉर्ट	चयन क्रम	सम्मिलन क्रमबद्ध करें	मर्ज सॉर्ट	त्वरित क्रमित करें	हीप सॉर्ट
सर्वश्रेष्ठ मामला	O(n² )	O(n² )	ओ(एन)	O(लॉग n)	O(लॉग n)	O(logn)
औसत मामला	O(n² )	O(n² )	O(n² )	O(लॉग n)	O(लॉग n)	O(लॉग n)
सबसे खराब स्थिति	O(n²⁾	O(n² )	O(n² )	O(लॉग n)	O(n² )	O(लॉग n)

कुछ सॉर्टिंग एल्गोरिदम गैर-तुलना आधारित एल्गोरिदम हैं। उनमें से कुछ रेडिक्स सॉर्ट, बकेट सॉर्ट, काउंट सॉर्ट हैं। ये गैर-तुलना आधारित सॉर्ट हैं क्योंकि यहां दो तत्वों की तुलना सॉर्टिंग के दौरान नहीं की जाती है। तकनीकें थोड़ी अलग हैं। अब हम विभिन्न प्रकार के विश्लेषण के आधार पर उनके बीच अंतर देखेंगे।

विश्लेषण प्रकार	रेडिक्स सॉर्ट (k अधिकतम अंक है)	काउंटिंग सॉर्ट (k काउंट एरे का आकार है)	बकेट सॉर्ट (k बाल्टी की संख्या है)
सर्वश्रेष्ठ मामला	ओ(एनके)	O(n + k)	O(n + k)
औसत मामला	ओ(एनके)	O(n + k)	O(n + k)
सबसे खराब स्थिति	ओ(एनके)	O(n + k)	O(n² )

छँटाई तकनीकों की तुलना कुछ अन्य मापदंडों का उपयोग करके भी की जा सकती है। कुछ सॉर्टिंग एल्गोरिदम इन-प्लेस सॉर्टिंग एल्गोरिदम हैं, और कुछ आउट-प्लेस सॉर्टिंग एल्गोरिदम हैं। वे एल्गोरिदम, जिन्हें किसी अतिरिक्त स्थान की आवश्यकता नहीं होती है, उन्हें इन-प्लेस सॉर्टिंग एल्गोरिदम कहा जाता है। जैसे कि क्विकॉर्ट, हीपसॉर्ट एल्गोरिदम जगह में हैं। लेकिन मर्ज सॉर्ट आउट-प्लेस सॉर्टिंग तकनीक है।

कुछ एल्गोरिदम ऑनलाइन हैं और कुछ ऑफलाइन हैं। यदि छँटाई प्रक्रिया चल रही है, तो एल्गोरिथ्म नए तत्व को स्वीकार करता है, जिसे ऑनलाइन छँटाई एल्गोरिथ्म कहा जाता है। ऊपर बताई गई तकनीकों से, सम्मिलन प्रकार ऑनलाइन छँटाई तकनीक है।