यहां हम कुछ सॉर्टिंग मेथड्स देखेंगे। 200+ सॉर्टिंग तकनीकें हैं। हम उनमें से कुछ देखेंगे। कुछ सॉर्टिंग तकनीकें तुलना-आधारित सॉर्ट हैं, कुछ नॉन-कम्पेरिजन आधारित सॉर्टिंग तकनीक हैं।
कम्पेरिजन बेस्ड सॉर्टिंग तकनीकें हैं: बबल सॉर्ट, सिलेक्शन सॉर्ट, इन्सर्शन सॉर्ट, मर्ज सॉर्ट, क्विकसॉर्ट, हीप सॉर्ट आदि। इन तकनीकों को कम्पेरिजन बेस्ड सॉर्ट माना जाता है क्योंकि इन तकनीकों में मानों की तुलना की जाती है, और उन्हें अलग-अलग चरणों में सॉर्टेड स्थिति में रखा जाता है। यहां हम इन तकनीकों की समय जटिलता देखेंगे।
| विश्लेषण प्रकार | बबल सॉर्ट | सिलेक्शन सॉर्ट | इन्सर्शन सॉर्ट | मर्ज सॉर्ट | क्विक सॉर्ट | हीप सॉर्ट |
|---|---|---|---|---|---|---|
| बेस्ट केस | O(n²) | O(n²) | O(n) | O(log n) | O(log n) | O(log n) |
| औसत केस | O(n²) | O(n²) | O(n²) | O(log n) | O(log n) | O(log n) |
| वर्स्ट केस | O(n²) | O(n²) | O(n²) | O(log n) | O(n²) | O(log n) |
कुछ सॉर्टिंग एल्गोरिदम नॉन-कम्पेरिजन आधारित एल्गोरिदम हैं। उनमें से कुछ हैं: रेडिक्स सॉर्ट, बकेट सॉर्ट, काउंट सॉर्ट। ये नॉन-कम्पेरिजन बेस्ड सॉर्ट हैं क्योंकि यहां सॉर्टिंग करते समय दो एलिमेंट्स की तुलना नहीं की जाती। तकनीकें थोड़ी अलग हैं। अब हम विभिन्न प्रकार के विश्लेषण के आधार पर उनके बीच अंतर देखेंगे।
| विश्लेषण प्रकार | रेडिक्स सॉर्ट (k अधिकतम अंक है) | काउंटिंग सॉर्ट (k काउंट सरणी का आकार है) | बकेट सॉर्ट (k बकेट की संख्या है) |
|---|---|---|---|
| बेस्ट केस | O(nk) | O(n + k) | O(n + k) |
| औसत केस | O(nk) | O(n + k) | O(n + k) |
| वर्स्ट केस | O(nk) | O(n + k) | O(n²) |
सॉर्टिंग तकनीकों की तुलना कुछ अन्य पैरामीटर्स का उपयोग करके भी की जा सकती है। कुछ सॉर्टिंग एल्गोरिदम इन-प्लेस सॉर्टिंग एल्गोरिदम हैं, और कुछ आउट-ऑफ-प्लेस सॉर्टिंग एल्गोरिदम हैं। जिन एल्गोरिदम को किसी अतिरिक्त स्थान की आवश्यकता नहीं होती, उन्हें इन-प्लेस सॉर्टिंग एल्गोरिदम कहा जाता है। जैसे क्विकसॉर्ट, हीपसॉर्ट एल्गोरिदम इन-प्लेस हैं। लेकिन मर्ज सॉर्ट आउट-ऑफ-प्लेस सॉर्टिंग तकनीक है।
कुछ एल्गोरिदम ऑनलाइन हैं और कुछ ऑफलाइन। यदि एल्गोरिदम सॉर्टिंग प्रक्रिया चलने के दौरान नए एलिमेंट को स्वीकार करता है, तो उसे ऑनलाइन सॉर्टिंग एल्गोरिदम कहा जाता है। ऊपर उल्लिखित तकनीकों में से, इन्सर्शन सॉर्ट ऑनलाइन सॉर्टिंग तकनीक है।
