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

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

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

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

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

चयन सॉर्टिंग कैसे काम करता है?

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

उदाहरण

उदाहरण के लिए, यदि न्यूनतम मान का सूचकांक 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)

हमारे पास अविभाजित सूची में केवल एक मान बचा है। इसलिए, यह पहले से ही क्रमबद्ध है।

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

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

निम्नलिखित कोड चयन सॉर्ट कार्यान्वयन को दर्शाता है Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

उपरोक्त कोड चलाने से निम्नलिखित परिणाम प्राप्त होते हैं

[3, 6, 9, 21, 33]

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

कोड का स्पष्टीकरण इस प्रकार है

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

selectionSort नामक फ़ंक्शन को परिभाषित करता है
सूची में तत्वों की कुल संख्या प्राप्त करता है। मानों की तुलना करते समय किए जाने वाले पास की संख्या निर्धारित करने के लिए हमें इसकी आवश्यकता होती है।
बाहरी लूप। सूची के मानों के माध्यम से पुनरावृति करने के लिए लूप का उपयोग करता है। पुनरावृत्तियों की संख्या (n – 1) है। n का मान 5 है, इसलिए (5 – 1) हमें 4 देता है। इसका मतलब है कि बाहरी पुनरावृत्तियाँ 4 बार की जाएँगी। प्रत्येक पुनरावृत्ति में, चर i का मान चर minValueIndex को सौंपा जाता है।
आंतरिक लूप। सबसे बाएं मान की तुलना दाएं हाथ की ओर के अन्य मानों से करने के लिए लूप का उपयोग करता है। हालाँकि, j का मान इंडेक्स 0 से शुरू नहीं होता है। यह (i + 1) से शुरू होता है। यह उन मानों को बाहर करता है जिन्हें पहले ही सॉर्ट किया जा चुका है ताकि हम उन आइटम पर ध्यान केंद्रित कर सकें जिन्हें अभी तक सॉर्ट नहीं किया गया है।
अक्रमित सूची में न्यूनतम मान ढूँढता है और उसे उचित स्थान पर रखता है
जब स्वैपिंग स्थिति सत्य होती है तो minValueIndex का मान अपडेट करता है
सूचकांक संख्या minValueIndex और i के मानों की तुलना करके देखें कि क्या वे बराबर नहीं हैं
सबसे बाईं ओर का मान एक अस्थायी चर में संग्रहीत किया जाता है
दाएँ हाथ की ओर से निचला मान प्रथम स्थान पर आता है
अस्थायी मान में संग्रहीत मान उस स्थिति में संग्रहीत किया जाता है जो पहले न्यूनतम मान द्वारा धारण की गई थी
फ़ंक्शन परिणाम के रूप में सॉर्ट की गई सूची लौटाता है
एक सूची बनाता है जिसमें यादृच्छिक संख्याएँ होती हैं
el को पैरामीटर के रूप में पास करके चयन सॉर्ट फ़ंक्शन को कॉल करने के बाद सॉर्ट की गई सूची को प्रिंट करें।

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

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

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

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

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

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

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

चयन सॉर्ट की स्थान जटिलता O(1) है क्योंकि इसमें मानों की अदला-बदली के लिए एक अस्थायी चर की आवश्यकता होती है।

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

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

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

चयन सॉर्ट के लाभ

चयन सॉर्ट के लाभ निम्नलिखित हैं

यह छोटी सूचियों पर बहुत अच्छा प्रदर्शन करता है
यह एक इन-प्लेस एल्गोरिथम है। इसमें सॉर्टिंग के लिए बहुत ज़्यादा जगह की ज़रूरत नहीं होती। टेम्पोरल वैरिएबल को होल्ड करने के लिए सिर्फ़ एक अतिरिक्त जगह की ज़रूरत होती है।
यह पहले से ही सॉर्ट की गई वस्तुओं पर अच्छा प्रदर्शन करता है।

चयन क्रम के नुकसान

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

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

सारांश

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