सॉर्टिंग तकनीक, त्वरित सॉर्ट और मर्ज सॉर्ट डिवाइड और विजय विधि पर बनाए गए हैं, जिसमें तत्वों के समूह को विभाजित किया जाता है और फिर पुनर्व्यवस्था के बाद संयोजित किया जाता है। तत्वों के एक बड़े समूह को छांटने के लिए त्वरित प्रकार को आमतौर पर मर्ज सॉर्ट की तुलना में अधिक तुलना की आवश्यकता होती है।
तुलना चार्ट
| तुलना के लिए आधार | जल्दी से सुलझाएं | मर्ज़ सॉर्ट |
|---|---|---|
| एरे में तत्वों का विभाजन | तत्वों की सूची का विभाजन आवश्यक रूप से आधे में विभाजित नहीं है। | सरणी को हमेशा आधे (n / 2) में विभाजित किया जाता है। |
| सबसे खराब मामला जटिलता | हे (एन 2) | ओ (एन लॉग एन) |
| पर अच्छी तरह से काम करता है | छोटा सा सरणी | किसी भी प्रकार के सरणी में ठीक काम करता है। |
| गति | छोटे डेटा सेट के लिए अन्य छँटाई एल्गोरिदम की तुलना में तेज़। | सभी प्रकार के डेटा सेटों में लगातार गति। |
| अतिरिक्त भंडारण स्थान की आवश्यकता | कम | अधिक |
| दक्षता | बड़े सरणियों के लिए अक्षम। | अधिक कुशल। |
| छँटाई विधि | अंदर का | बाहरी |
क्विक सॉर्ट की परिभाषा
त्वरित प्रकार व्यापक रूप से एल्गोरिथ्म का उपयोग किया जाता है क्योंकि यह लघु सरणियों के लिए तेज़ होता है। तत्वों के सेट को बार-बार भागों में विभाजित किया जाता है जब तक कि इसे आगे विभाजित करना संभव न हो। क्विक सॉर्ट को पार्टीशन एक्सचेंज सॉर्ट के रूप में भी जाना जाता है। यह तत्वों के विभाजन के लिए एक प्रमुख तत्व (धुरी के रूप में जाना जाता है) का उपयोग करता है। एक विभाजन में वे तत्व होते हैं जो प्रमुख तत्व से छोटे होते हैं। एक अन्य विभाजन में वे तत्व शामिल हैं जो प्रमुख तत्व से अधिक हैं। तत्वों को पुनरावर्ती रूप से क्रमबद्ध किया जाता है।
मान लीजिए कि एक ए संख्या है [ए] 1, ए [2], ए [3], …… .., ए [एन] एन संख्या की जिन्हें क्रमबद्ध किया जाना है। त्वरित सॉर्ट एल्गोरिथ्म में निम्नलिखित चरण शामिल थे।
- पहला तत्व या कुंजी के रूप में चुना गया कोई भी यादृच्छिक तत्व, मान = A (1)।
- "कम" पॉइंटर को दूसरे स्थान पर रखा गया है और "अप" पॉइंटर को एरे के अंतिम तत्व पर रखा गया है, अर्थात निम्न = 2 और अप = एन;
- लगातार, एक स्थिति तक "कम" सूचक को बढ़ाएँ (ए [कम]> कुंजी)।
- लगातार, जब तक (एक [ऊपर] <= कुंजी) तक "अप" पॉइंटर को एक स्थिति से बढ़ाएं।
- यदि अप, ए [अप] के साथ कम इंटरचेंज ए [कम] से अधिक है।
- चरण 3, 4 और 5 को तब तक दोहराएं जब तक कि चरण 5 में स्थिति विफल न हो जाए (अर्थात <= कम) तब कुंजी के साथ ए [अप] को इंटरचेंज करें।
- यदि कुंजी के बचे हुए तत्व कुंजी से छोटे हैं और कुंजी के सही तत्व कुंजी से अधिक हैं, तो सरणी को दो उप-सरणियों में विभाजित किया गया है।
- उपरोक्त प्रक्रिया बार-बार सबरेज़ पर लागू होती है जब तक कि संपूर्ण सरणी को सॉर्ट नहीं किया जाता है।
फायदे और नुकसान
इसमें एक अच्छा औसत व्यवहार होता है। क्विक सॉर्ट की रनिंग टाइम जटिलता अच्छी है कि यह एल्गोरिदम जैसे बबल सॉर्ट, इंसर्शन सॉर्ट और सिलेक्शन सॉर्ट से तेज है। हालांकि, यह जटिल और बहुत पुनरावर्ती है, यही कारण है कि यह बड़े सरणियों के लिए उपयुक्त नहीं है।
मर्ज सॉर्ट की परिभाषा
मर्ज सॉर्ट एक बाहरी एल्गोरिथ्म है जो विभाजन और जीत की रणनीति पर आधारित है। तत्वों को उप-सरणियों (n / 2) में बार-बार विभाजित किया जाता है जब तक कि केवल एक तत्व नहीं छोड़ा जाता है, जो क्रमबद्ध समय को काफी कम कर देता है। यह सहायक सरणी के भंडारण के लिए अतिरिक्त भंडारण का उपयोग करता है। मर्ज सॉर्ट तीन सरणियों का उपयोग करता है जहां दो का उपयोग प्रत्येक आधे को संग्रहीत करने के लिए किया जाता है, और तीसरे सॉर्ट का उपयोग अंतिम सॉर्ट की गई सूची को संग्रहीत करने के लिए किया जाता है। प्रत्येक सरणी को पुनरावर्ती रूप से सॉर्ट किया जाता है। अंत में, यह सरणी के n तत्व का आकार बनाने के लिए सबरेज़ को मर्ज किया जाता है। सूची हमेशा त्वरित क्रमबद्ध करने के लिए केवल आधे (n / 2) प्रसार में विभाजित है।
आज्ञा देना A की संख्या n तत्वों की संख्या को A [1], A [2], ………, A [n] क्रमबद्ध किया जाएगा। मर्ज सॉर्ट दिए गए चरणों का अनुसरण करता है।
- सरणी A को लगभग n / 2 में विभाजित करके उप-सरणी को 2 से विभाजित करें, जिसका अर्थ है कि (A [1], A [2]), (A [3], A [4]), (A] में तत्व k], A [k + 1]), (A [n-1], A [n]) उप-सरणियाँ क्रमबद्ध क्रम में होनी चाहिए।
- आकार 4 के क्रमबद्ध उपप्रकारों की सूची प्राप्त करने के लिए प्रत्येक जोड़े के जोड़े को मिलाएं; तत्वों में तत्व भी क्रमबद्ध क्रम में होते हैं, (A [1], [[2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + २]], ……। (A [n-३], A [n-२], A [n-१], A [n])।
- चरण 2 को बार-बार किया जाता है जब तक कि आकार n का केवल एक छांटा गया सरणी न हो।
फायदे और नुकसान
मर्ज सॉर्ट एल्गोरिथ्म छँटाई में शामिल तत्वों की संख्या की परवाह किए बिना सटीक और सटीक तरीके से करता है। यह बड़े डेटा सेट के साथ भी ठीक काम करता है। हालाँकि, यह मेमोरी के बड़े हिस्से की खपत करता है।
क्विक सॉर्ट और मर्ज सॉर्ट के बीच मुख्य अंतर
- मर्ज सॉर्ट में, सरणी को केवल दो हिस्सों (यानी n / 2) में विभाजित किया जाना चाहिए। जैसा कि, त्वरित प्रकार में, सूची को समान तत्वों में विभाजित करने की कोई अनिवार्यता नहीं है।
- त्वरित प्रकार की सबसे खराब स्थिति O (n2) है क्योंकि यह सबसे खराब स्थिति में बहुत अधिक तुलना करता है। इसके विपरीत, मर्ज सॉर्ट में एक ही सबसे खराब स्थिति और औसत केस जटिलताएं हैं, वह है ओ (एन लॉग एन)।
- मर्ज सॉर्ट किसी भी प्रकार के डेटा सेट पर अच्छी तरह से काम कर सकता है चाहे वह बड़ा हो या छोटा। इसके विपरीत, त्वरित सॉर्ट बड़े डेटासेट के साथ अच्छी तरह से काम नहीं कर सकता है।
- त्वरित सॉर्ट कुछ मामलों में मर्ज सॉर्ट की तुलना में तेज़ है जैसे कि छोटे डेटा सेट के लिए।
- मर्ज सॉर्ट के लिए सहायक सरणियों को संग्रहीत करने के लिए अतिरिक्त मेमोरी स्पेस की आवश्यकता होती है। दूसरी ओर, त्वरित प्रकार को अतिरिक्त संग्रहण के लिए अधिक स्थान की आवश्यकता नहीं होती है।
- त्वरित सॉर्ट की तुलना में मर्ज सॉर्ट अधिक कुशल है।
- त्वरित सॉर्ट आंतरिक सॉर्टिंग विधि है जहां डेटा को सॉर्ट करना है जो मुख्य मेमोरी में एक समय में समायोजित किया जाता है। इसके विपरीत, मर्ज सॉर्ट बाहरी सॉर्टिंग विधि है जिसमें डेटा को सॉर्ट किया जाना है और एक ही समय में मेमोरी में समायोजित नहीं किया जा सकता है और कुछ को सहायक मेमोरी में रखा जाना चाहिए।
निष्कर्ष
त्वरित सॉर्ट तेजी से मामले हैं, लेकिन कुछ स्थितियों में अक्षम है और मर्ज सॉर्ट की तुलना में बहुत अधिक तुलना करता है। हालांकि मर्ज सॉर्ट के लिए कम तुलना की आवश्यकता होती है, इसे अतिरिक्त सरणी को संग्रहीत करने के लिए 0 (n) के अतिरिक्त मेमोरी स्पेस की आवश्यकता होती है जबकि त्वरित सॉर्ट में O (लॉग एन) के स्थान की आवश्यकता होती है।
