सॉर्टिंग एक बुनियादी ऑपरेशन है जिसमें किसी सरणी के तत्वों को उसकी खोज क्षमता को बढ़ाने के लिए कुछ विशिष्ट क्रम में व्यवस्थित किया जाता है। सरल शब्दों में, डेटा को क्रमबद्ध किया जाता है ताकि इसे आसानी से खोजा जा सके।
तुलना चार्ट
| तुलना के लिए आधार | सम्मिलन सॉर्ट | चयन छांटना |
|---|---|---|
| बुनियादी | मौजूदा सॉर्ट की गई फ़ाइल में डेटा सम्मिलित करके डेटा को सॉर्ट किया जाता है। | डेटा को सॉर्ट किए गए स्थान में लगातार तत्वों का चयन और रखकर सॉर्ट किया जाता है। |
| प्रकृति | स्थिर | अस्थिर |
| प्रक्रिया का पालन किया जाना है | तत्वों को पहले से ही जाना जाता है, जबकि उन्हें रखने के लिए स्थान खोजा जाता है। | स्थान पहले से ज्ञात है जबकि तत्वों की खोज की जाती है। |
| तत्काल डेटा | प्रविष्टि सॉर्ट लाइव छँटाई तकनीक है जो तत्काल डेटा से निपट सकती है। | यह तत्काल डेटा के साथ सौदा नहीं कर सकता है, इसे शुरुआत में मौजूद रहने की आवश्यकता है। |
| सबसे अच्छा मामला जटिलता | पर) | ओ (एन 2 ) |
सम्मिलन की परिभाषा
प्रविष्टि सॉर्ट मौजूदा सॉर्ट की गई फ़ाइल में मानों के सेट को सम्मिलित करके काम करता है। यह एक बार में एक तत्व को सम्मिलित करके क्रमबद्ध सरणी का निर्माण करता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि किसी क्रम में पूरे सरणी को क्रमबद्ध नहीं किया जाता। प्रविष्टि प्रकार के पीछे प्राथमिक अवधारणा प्रत्येक आइटम को अंतिम सूची में उसके उपयुक्त स्थान पर सम्मिलित करना है। सम्मिलन सॉर्ट विधि स्मृति की प्रभावी मात्रा को बचाता है।
सम्मिलन के प्रकार का कार्य करना
- यह एरे के दो सेटों का उपयोग करता है जहां एक सॉर्ट किए गए डेटा और अन्य को अनसोल्ड डेटा स्टोर करता है।
- सॉर्टिंग एल्गोरिथ्म तब तक काम करता है जब तक कि अनसर्टेड सेट में तत्व न हों।
- मान लेते हैं कि सरणी में 'n' संख्या तत्व हैं। प्रारंभ में, अनुक्रमित 0 (LB = 0) के साथ तत्व हल सेट में मौजूद है। शेष तत्व सूची के अनियोजित विभाजन में हैं।
- अनसर्टेड पार्ट के पहले एलिमेंट में अरे इंडेक्स 1 (यदि एलबी = 0) है।
- प्रत्येक पुनरावृत्ति के बाद, यह बिना विभाजन के पहले तत्व को चुनता है और इसे सॉर्ट किए गए सेट में उचित स्थान पर सम्मिलित करता है।
प्रविष्टि प्रकार के लाभ
- डेटा के छोटे सेट के साथ उपयोग किए जाने पर आसानी से कार्यान्वित और बहुत कुशल।
- सम्मिलन प्रकार की अतिरिक्त मेमोरी स्थान की आवश्यकता कम है (यानी, ओ (1))।
- इसे लाइव सॉर्टिंग तकनीक माना जाता है क्योंकि सूची को नए तत्वों को प्राप्त करने के लिए क्रमबद्ध किया जा सकता है।
- यह अन्य छँटाई एल्गोरिदम की तुलना में तेज़ है।
उदाहरण :
चयन सॉर्ट की परिभाषा
चयन सॉर्ट न्यूनतम मान संख्या की खोज करके और क्रम (आरोही या अवरोही) के अनुसार पहली या अंतिम स्थिति में रखकर छँटाई करता है। न्यूनतम कुंजी को खोजने और उसे उचित स्थिति में रखने की प्रक्रिया तब तक जारी रखी जाती है जब तक कि सभी तत्वों को सही स्थिति में नहीं रखा जाता है।
चयन सॉर्ट का कार्य करना
- स्मृति में एन तत्वों के साथ एक सरणी एआरआर मान लीजिए।
- पहले पास में, सबसे छोटी कुंजी को उसकी स्थिति के साथ खोजा जाता है फिर ARR [POS] को ARR [0] के साथ स्वैप किया जाता है। इसलिए, ARR [0] क्रमबद्ध है।
- दूसरे पास में, फिर से एन -1 तत्वों की उप-श्रेणी में सबसे छोटे मूल्य की स्थिति निर्धारित की जाती है। ARR [1] के साथ ARR [POS] को इंटरचेंज करें।
- पास एन -1 में, तत्वों की एन संख्या को सॉर्ट करने के लिए एक ही प्रक्रिया की जाती है।
उदाहरण :
प्रविष्टि सॉर्ट और चयन सॉर्ट के बीच महत्वपूर्ण अंतर
- प्रविष्टि प्रकार आमतौर पर सम्मिलित ऑपरेशन करता है। इसके विपरीत, चयन प्रकार आवश्यक तत्वों के चयन और स्थिति को पूरा करता है।
- प्रविष्टि सॉर्ट को स्थिर कहा जाता है जबकि चयन सॉर्ट एक स्थिर एल्गोरिथ्म नहीं है।
- सम्मिलन सॉर्ट एल्गोरिथ्म में तत्वों को पहले से जाना जाता है। इसके विपरीत, चयन प्रकार में पहले से स्थान होता है।
- सम्मिलन सॉर्ट एक लाइव सॉर्टिंग तकनीक है जहां पहुंचने वाले तत्वों को सूची में तुरंत सॉर्ट किया जाता है जबकि चयन सॉर्ट तत्काल डेटा के साथ अच्छी तरह से काम नहीं कर सकता है।
- प्रविष्टि प्रकार में O (n) सबसे अच्छा स्थिति में चलने का समय होता है। के रूप में, चयन के प्रकार का सबसे अच्छा मामला रन टाइम जटिलता हे (n2) है।
सम्मिलन प्रकार की जटिलता
सम्मिलन प्रकार की सबसे अच्छी स्थिति जटिलता हे (n) बार, यानी जब सरणी पहले से छाँटी जाती है। उसी तरह, जब सरणी को रिवर्स ऑर्डर में सॉर्ट किया जाता है, तो सॉर्ट किए गए सेट में प्रत्येक तत्व के साथ अनसोल्ड सरणी के पहले तत्व की तुलना की जाती है। तो, सबसे खराब स्थिति में, सम्मिलन प्रकार का चलने का समय द्विघात है, अर्थात, ओ (एन 2) । औसत मामले में भी इसे न्यूनतम (k-1) / 2 तुलना करना पड़ता है। इसलिए, औसत मामले में द्विघात रनिंग टाइम O (n2) भी है।
चयन सॉर्ट की जटिलता
चयन के कार्य के रूप में, सरणी में तत्वों के मूल क्रम पर निर्भर नहीं होता है, इसलिए चयन मामले में सबसे अच्छा मामला और सबसे खराब स्थिति जटिलता के बीच बहुत अंतर नहीं है।
चयन प्रकार न्यूनतम मूल्य तत्व का चयन करता है, चयन प्रक्रिया में सभी 'एन' तत्वों की संख्या स्कैन की जाती है; इसलिए पहले पास में n-1 तुलना की जाती है। फिर, तत्वों को आपस में जोड़ा जाता है। इसी तरह दूसरे पास में भी दूसरे सबसे छोटे तत्व को खोजने के लिए हमें बाकी n-1 तत्वों की स्कैनिंग की आवश्यकता होती है और यह प्रक्रिया पूरी तरह से समाप्त होने तक जारी रहती है।
इस प्रकार, चयन प्रकार की समय जटिलता O (n2) है ।
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
निष्कर्ष
छँटाई एल्गोरिथ्म के दोनों के बीच, सम्मिलन प्रकार तेज, कुशल, स्थिर है जबकि चयन सॉर्ट केवल कुशलता से काम करता है जब तत्वों का छोटा सेट शामिल होता है या सूची आंशिक रूप से पहले सॉर्ट होती है। चयन प्रकार द्वारा की गई तुलनाओं की संख्या प्रदर्शन किए गए आंदोलनों की तुलना में अधिक है जबकि सम्मिलन क्रम में किसी तत्व को स्थानांतरित करने या बदली गई संख्या की तुलना की गई तुलना में अधिक है।
