चयन क्रमबद्ध: एल्गोरिथम को पायथन कोड उदाहरण के साथ समझाया गया

चयन सॉर्ट क्या है?

चयन प्रकार एक तुलना छँटाई एल्गोरिथ्म है जो बढ़ते क्रम में वस्तुओं की एक यादृच्छिक सूची को सॉर्ट करने के लिए उपयोग किया जाता है। तुलना के लिए बहुत अधिक अतिरिक्त स्थान की आवश्यकता नहीं है। यह केवल अस्थायी चर के लिए एक अतिरिक्त मेमोरी स्थान की आवश्यकता है।

इसे इन-प्लेस सॉर्टिंग के रूप में जाना जाता है । चयन प्रकार में O (n ² ) की समय जटिलता है जहाँ n सूची में कुल आइटम है। समय जटिलता सूची को क्रमबद्ध करने के लिए आवश्यक पुनरावृत्तियों की संख्या को मापती है। सूची को दो भागों में विभाजित किया गया है: पहली सूची में छांटे गए आइटम होते हैं, जबकि दूसरी सूची में अनसोल्ड आइटम होते हैं।

डिफ़ॉल्ट रूप से, सॉर्ट की गई सूची खाली है, और अनसोल्ड सूची में सभी तत्व शामिल हैं। फिर अनसोल्ड सूची को न्यूनतम मान के लिए स्कैन किया जाता है, जिसे बाद में क्रमबद्ध सूची में रखा जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि सभी मूल्यों की तुलना और छँटाई नहीं हो जाती।

इस एल्गोरिथ्म ट्यूटोरियल में, आप सीखेंगे:

• चयन सॉर्ट क्या है?
• चयन प्रकार कैसे काम करता है?
• समस्या की परिभाषा
• समाधान (एल्गोरिथम)
• दृश्य प्रतिनिधित्व
• पायथन 3 का उपयोग करके चयन सॉर्ट प्रोग्राम
• कोड स्पष्टीकरण
• चयन की समय जटिलता
• चयन प्रकार का उपयोग कब करें?
• चयन के प्रकार
• चयन सॉर्ट के नुकसान

चयन प्रकार कैसे काम करता है?

अनसोर्स्ड पार्टीशन में पहला आइटम सभी मानों के साथ तुलना करने के लिए है कि यह न्यूनतम मूल्य है या नहीं यह जांचने के लिए दाएं हाथ की तरफ से। यदि यह न्यूनतम मूल्य नहीं है, तो इसकी स्थिति को न्यूनतम मूल्य से बदल दिया जाता है।

उदाहरण:

• उदाहरण के लिए, यदि न्यूनतम मान का इंडेक्स 3 है, तो इंडेक्स 3 वाले तत्व का मान इंडेक्स 0 पर रखा गया है, जबकि इंडेक्स 0 पर था वैल्यू को इंडेक्स 3 में रखा गया है। न्यूनतम मूल्य, फिर वह अपने पदों को लौटाता है।
• वह तत्व जो न्यूनतम मूल्य के रूप में निर्धारित किया गया है, फिर बाईं ओर विभाजन पर ले जाया जाता है, जो क्रमबद्ध सूची है।
• विभाजन वाले पक्ष में अब एक तत्व होता है, जबकि अनपार्टेड पक्ष में (n - 1) तत्व होते हैं जहाँ n सूची में कुल तत्वों की संख्या होती है। यह प्रक्रिया बार-बार दोहराई जाती है जब तक कि सभी वस्तुओं की उनके मूल्यों के आधार पर तुलना और छंटनी नहीं की जाती है।

समस्या की परिभाषा

ऐसे तत्वों की सूची जो यादृच्छिक क्रम में हैं, उन्हें आरोही क्रम में क्रमबद्ध करने की आवश्यकता है। एक उदाहरण के रूप में निम्नलिखित सूची पर विचार करें।

[21,6,9,33,3]

उपरोक्त सूची को निम्न परिणामों का उत्पादन करने के लिए क्रमबद्ध किया जाना चाहिए

[3,6,9,21,33]

समाधान (एल्गोरिथम)

चरण 1) n का मान प्राप्त करें जो कि सरणी का कुल आकार है

चरण 2) सूची को सॉर्ट किए गए और अनसोल्ड सेक्शन में विभाजित करें। सॉर्ट किया गया अनुभाग प्रारंभ में रिक्त है जबकि अनसेक्ड अनुभाग में पूरी सूची है

चरण 3) गैर-खंड से न्यूनतम मान चुनें और इसे छाँटे गए अनुभाग में रखें।

चरण 4) प्रक्रिया को दोहराएं (n - 1) बार जब तक कि सूची के सभी तत्व क्रमबद्ध न हो जाएं।

दृश्य प्रतिनिधित्व

पांच तत्वों की सूची को देखते हुए, निम्नलिखित चित्र बताते हैं कि चयन सॉर्ट एल्गोरिथ्म कैसे उन्हें छांटते समय मूल्यों के माध्यम से पुनरावृत्त होता है।

निम्न छवि अनसोल्ड सूची को दिखाती है

चरण 1)

पहले मान 21 की तुलना बाकी मानों के साथ की जाती है ताकि यह जांचा जा सके कि यह न्यूनतम मूल्य है या नहीं।

3 न्यूनतम मान है, इसलिए 21 और 3 की स्थिति बदली हुई है। हरे रंग की पृष्ठभूमि वाले मान सूची के क्रमबद्ध विभाजन का प्रतिनिधित्व करते हैं।

चरण 2)

वैल्यू 6 जो अनसोर्स्ड पार्टीशन में पहला एलिमेंट है, उसकी तुलना बाकी वैल्यूज़ के साथ की जाती है ताकि पता लगाया जा सके कि लोअर वैल्यू मौजूद है या नहीं

मान 6 न्यूनतम मान है, इसलिए यह अपनी स्थिति बनाए रखता है।

चरण 3)

9 के मान के साथ अनसोल्ड सूची के पहले तत्व की तुलना बाकी मानों के साथ की जाती है ताकि यह जांचा जा सके कि यह न्यूनतम मूल्य है या नहीं।

मान 9 न्यूनतम मान है, इसलिए यह सॉर्ट किए गए विभाजन में अपनी स्थिति बनाए रखता है।

चरण 4)

मूल्य 33 की तुलना बाकी मूल्यों के साथ की जाती है।

मान 21 33 से कम है, इसलिए उपरोक्त नई सूची का उत्पादन करने के लिए पदों की अदला-बदली की जाती है।

चरण 5)

हमारे पास केवल एक मूल्य सूची में नहीं बचा है। इसलिए, यह पहले से ही सॉर्ट किया गया है।

अंतिम सूची ऊपर की छवि में दिखाए गए की तरह है।

पायथन 3 का उपयोग करके चयन सॉर्ट प्रोग्राम

निम्नलिखित कोड पायथन 3 का उपयोग करके चयन प्रकार के कार्यान्वयन को दर्शाता है

def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

उपरोक्त कोड चलाएँ निम्नलिखित परिणाम उत्पन्न करता है

[3, 6, 9, 21, 33]

कोड स्पष्टीकरण

कोड के लिए स्पष्टीकरण निम्नानुसार है

यहाँ कोड स्पष्टीकरण है:

1. एक फ़ंक्शन का चयन करता है जिसका नाम SelectionSort है
2. सूची में तत्वों की कुल संख्या हो जाती है। मूल्यों की तुलना करते समय किए जाने वाले पास की संख्या निर्धारित करने के लिए हमें इसकी आवश्यकता है।
3. बाहरी पाश। सूची के मूल्यों के माध्यम से पुनरावृति करने के लिए लूप का उपयोग करता है। पुनरावृत्तियों की संख्या है (n - 1)। N का मान 5 है, इसलिए (5 - 1) हमें 4 देता है। इसका मतलब है कि बाहरी पुनरावृत्तियों को 4 बार किया जाएगा। प्रत्येक पुनरावृत्ति में, चर I का मान चर minValueIndex को सौंपा गया है
4. आंतरिक फंदे। दाएं हाथ की ओर के अन्य मूल्यों के लिए बाईं ओर के मूल्य की तुलना करने के लिए लूप का उपयोग करता है। हालांकि, जे के लिए मूल्य सूचकांक 0. पर शुरू नहीं होता है। यह (i + 1) से शुरू होता है। यह उन मानों को बाहर करता है जो पहले से ही छंटे हुए हैं ताकि हम उन वस्तुओं पर ध्यान केंद्रित करें जो अभी तक छंटनी नहीं हुई हैं।
5. अनसोल्ड लिस्ट में न्यूनतम मूल्य को ढूँढता है और उसे उसकी उचित स्थिति में रखता है
6. स्वैपिंग की स्थिति सही होने पर minValueIndex के मान को अपडेट करता है
7. सूचकांक संख्या के मूल्यों की तुलना करता है minValueIndex और मैं यह देखने के लिए कि क्या वे समान नहीं हैं
8. बाईं ओर का मान एक अस्थायी चर में संग्रहीत किया जाता है
9. दाएं हाथ से कम मूल्य स्थिति पहली स्थिति लेता है
10. अस्थायी मूल्य में संग्रहीत मूल्य उस स्थिति में संग्रहीत किया जाता है जो पहले न्यूनतम मूल्य द्वारा आयोजित किया गया था
11. फ़ंक्शन परिणाम के रूप में क्रमबद्ध सूची देता है
12. एक सूची el बनाता है जिसमें यादृच्छिक संख्याएँ होती हैं
13. पैरामीटर के रूप में एल में गुजरने वाले चयन सॉर्ट फ़ंक्शन को कॉल करने के बाद सॉर्ट की गई सूची को प्रिंट करें।

चयन की समय जटिलता

सूची को सॉर्ट करने में लगने वाले निष्पादन समय की संख्या को व्यक्त करने के लिए सॉर्ट जटिलता का उपयोग किया जाता है। कार्यान्वयन में दो छोर हैं।

बाहरी लूप जो सूची से एक-एक करके मानों को चुनता है, उसे n बार निष्पादित किया जाता है जहां n सूची में मानों की कुल संख्या है।

आंतरिक लूप, जो बाहरी लूप से मूल्य की तुलना बाकी मूल्यों के साथ करता है, को भी एन बार निष्पादित किया जाता है जहां n सूची में तत्वों की कुल संख्या है।

इसलिए, निष्पादन की संख्या (n * n) है, जिसे O (n ² ) के रूप में भी व्यक्त किया जा सकता है ।

चयन प्रकार में जटिलता की तीन श्रेणियां हैं;

• सबसे खराब स्थिति - यह वह जगह है जहां प्रदान की गई सूची अवरोही क्रम में है। एल्गोरिथ्म अधिकतम निष्पादित करता है जिसे [बिग-ओ] ओ (एन ² ) के रूप में व्यक्त किया जाता है।
• सर्वश्रेष्ठ मामला - यह तब होता है जब प्रदान की गई सूची पहले से ही सॉर्ट की जाती है। एल्गोरिथ्म निष्पादन की न्यूनतम संख्या करता है जिसे [बिग-ओमेगा] n (n ² ) के रूप में व्यक्त किया जाता है
• औसत मामला - यह तब होता है जब सूची यादृच्छिक क्रम में होती है। औसत जटिलता के रूप में व्यक्त किया जाता है [बिग-थीटा] n (एन ² )

चयन प्रकार में O (1) की एक अंतरिक्ष जटिलता है क्योंकि इसमें स्वैपिंग मूल्यों के लिए उपयोग किए जाने वाले एक लौकिक चर की आवश्यकता होती है।

चयन प्रकार का उपयोग कब करें?

जब आप चाहते हैं तो चयन प्रकार का सबसे अच्छा उपयोग किया जाता है:

• आपको आरोही क्रम में वस्तुओं की एक छोटी सूची को क्रमबद्ध करना होगा
• जब स्वैपिंग मूल्यों की कीमत नगण्य है
• इसका उपयोग तब भी किया जाता है जब आपको यह सुनिश्चित करने की आवश्यकता होती है कि सूची के सभी मूल्यों की जाँच की गई है।

चयन के प्रकार

चयन के प्रकार निम्नलिखित हैं

• यह छोटी सूचियों पर बहुत अच्छा प्रदर्शन करता है
• यह एक इन-प्लेस एल्गोरिथम है। इसमें छंटाई के लिए बहुत अधिक जगह की आवश्यकता नहीं होती है। लौकिक चर को धारण करने के लिए केवल एक अतिरिक्त स्थान की आवश्यकता होती है।
• यह उन वस्तुओं पर अच्छा प्रदर्शन करता है जो पहले से ही छांटे गए हैं।

चयन सॉर्ट के नुकसान

चयन प्रकार के नुकसान निम्नलिखित हैं।

• यह बड़ी सूचियों पर काम करते समय खराब प्रदर्शन करता है।
• छँटाई के दौरान किए गए पुनरावृत्तियों की संख्या n-वर्ग है, जहाँ n सूची में तत्वों की कुल संख्या है।
• अन्य एल्गोरिदम, जैसे क्विकसॉर्ट, में चयन प्रकार की तुलना में बेहतर प्रदर्शन होता है।

सारांश:

• चयन सॉर्ट एक इन-प्लेस तुलना एल्गोरिथ्म है जिसका उपयोग किसी क्रमबद्ध सूची में यादृच्छिक सूची को सॉर्ट करने के लिए किया जाता है। इसमें O (n ² ) की समय जटिलता है
• सूची को दो खंडों में विभाजित किया गया है, क्रमबद्ध और अनसुलझा। न्यूनतम मान को अनसोल्ड सेक्शन से उठाया जाता है और सॉर्ट किए गए सेक्शन में रखा जाता है।
• यह बात तब तक दोहराई जाती है जब तक कि सभी आइटम सॉर्ट नहीं हो जाते।
• पायथन 3 में स्यूडोकोड को लागू करने में दो छोरों का उपयोग करना शामिल है और यदि स्वैप करना आवश्यक है तो जांच के लिए बयान
• समय जटिलता सूची को क्रमबद्ध करने के लिए आवश्यक कदमों की संख्या को मापती है।
• सबसे खराब स्थिति समय की जटिलता तब होती है जब सूची अवरोही क्रम में होती है। इसकी एक समय जटिलता है [बिग-ओ] ओ (एन ² )
• सबसे अच्छा मामला समय जटिलता तब होती है जब सूची पहले से ही बढ़ते क्रम में है। इसमें [बिग-ओमेगा] n (n ² ) की समय जटिलता है
• औसत-क्रम समय जटिलता तब होती है जब सूची यादृच्छिक क्रम में होती है। इसकी एक समय जटिलता है [बिग-थीटा] n (n ² )
• चयन सॉर्ट का सबसे अच्छा उपयोग किया जाता है जब आपके पास सॉर्ट करने के लिए मदों की एक छोटी सूची होती है, स्वैप मूल्यों की कीमत कोई फर्क नहीं पड़ता है, और सभी मूल्यों की जांच अनिवार्य है।
• चयन सूची विशाल सूचियों पर अच्छा प्रदर्शन नहीं करती है
• अन्य सॉर्टिंग एल्गोरिदम, जैसे क्विकॉर्ट, का चयन सॉर्ट की तुलना में बेहतर प्रदर्शन होता है।