पायथन इंसर्शन सॉर्ट कैसे लिखें

पायथन इंसर्शन सॉर्ट कैसे लिखें

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

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

इंसर्शन सॉर्ट एक ऐरे में प्रत्येक पुनरावृत्ति के बाद एक अनसॉर्ट किए गए तत्व को उसकी सही जगह पर रखता है।

इस गाइड में, हम बात करेंगे कि इंसर्शन सॉर्ट क्या हैं और वे कैसे काम करते हैं। हम एक उदाहरण के संदर्भ में पायथन में इंसर्शन सॉर्ट को कैसे लागू करें, इस पर चर्चा करेंगे, ताकि आप इस सॉर्टिंग एल्गोरिदम के साथ शुरुआत कर सकें।

पायथन इंसर्शन सॉर्ट क्या है?

एक इंसर्शन सॉर्ट एक सूची को दो उप-सूचियों में विभाजित करता है: सॉर्ट की गई और अनसॉर्ट की गई। यह फिर अनसॉर्ट की गई सूची में प्रत्येक तत्व की तुलना करता है और तब तक ऐसा करना जारी रखता है जब तक सूची में प्रत्येक आइटम सॉर्ट नहीं हो जाता।

एक इंसर्शन सॉर्ट एल्गोरिदम एक सॉर्ट किए गए आइटम को सॉर्ट की गई उप-सूची में ले जाता है और उसे अनसॉर्ट की गई उप-सूची से हटा देता है। दोनों उप-सूचियाँ एक ही ऐरे का हिस्सा हैं, लेकिन वे भेद करती हैं कि कोई आइटम सॉर्ट किया गया है या नहीं।

आप इंसर्शन सॉर्ट को कार्ड गेम में अपने हाथ में कार्ड्स के सेट को कैसे सॉर्ट करेंगे, उसके रूप में सोच सकते हैं।

आप कार्ड्स की सूची के माध्यम से एक-एक करके जाएंगे और उनकी तुलना एक दूसरे से करेंगे। सॉर्ट किए गए कार्ड आपके हाथ के बाईं ओर दिखाई देंगे। अनसॉर्ट किए गए कार्ड दाईं ओर तब तक दिखाई देंगे जब तक आप उन सभी को सॉर्ट नहीं कर लेते।

पायथन इंसर्शन सॉर्ट कैसे काम करते हैं?

आइए इंसर्शन सॉर्ट एल्गोरिदम का उपयोग करके एक ऐरे को सॉर्ट करने का काम शुरू करते हैं। निम्न अनसॉर्ट किए गए ऐरे पर विचार करें:

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

हमें current_number की तुलना ऐरे में पहले स्थान के आइटम से करने की आवश्यकता है। यदि current_number पहले तत्व से बड़ा है, तो यह उसी स्थान पर रहता है। अन्यथा, current_number को पहले तत्व के सामने ले जाया जाता है।

4, 9 से बड़ा नहीं है, इसलिए ये दो तत्व स्थान बदल लेते हैं।

हमारी सूची के पहले दो तत्व सॉर्ट किए गए हैं। अगला, हम current_number का मान सूची में तीसरे आइटम में बदलते हैं और इसकी तुलना इसके बाईं ओर के सभी आइटम्स से करते हैं।

हमारा current_number 3 बन जाता है। हमें तुलना करने की आवश्यकता है:

• क्या 3, 9 से बड़ा है? नहीं, इसलिए 3 को 9 से पहले डाला जाता है।
• क्या 3, 4 से बड़ा है? नहीं, इसलिए 3 को 4 से पहले ले जाया जाता है।

हमारी सूची अब इस तरह दिखती है:

यह प्रक्रिया तब तक दोहराई जाती है जब तक सूची सॉर्ट नहीं हो जाती। हमारी सूची में केवल तुलनाओं का एक और सेट करना बाकी है क्योंकि इसमें केवल चार मान हैं। अगली पुनरावृत्ति में, 5 current_number बन जाता है।

• क्या 5, 9 से बड़ा है? नहीं, इसलिए 5, 9 से पहले चला जाता है।

कोई और तुलना नहीं की जाती क्योंकि 5 हमारी सॉर्ट की गई सूची में अंतिम संख्या है। इस पुनरावृत्ति के बाद, हमारा ऐरे सॉर्ट हो गया है:

यह इतना सरल है! हमारे इंसर्शन सॉर्ट में, हमने हमेशा सॉर्ट किए गए मानों को सूची के बाईं ओर रखा। अनसॉर्ट किए गए मान दाईं ओर दिखाई दिए।

सूची में प्रत्येक पुनरावृत्ति के लिए, हमने current_number की तुलना सभी अनसॉर्ट किए गए आइटम्स से की। यह प्रक्रिया तब तक दोहराई गई जब तक हमारी सूची सॉर्ट नहीं हो गई।

पायथन में इंसर्शन सॉर्ट कैसे लिखें

कागज पर इंसर्शन सॉर्ट के माध्यम से चलना ठीक है। अब समय है कि हम इसमें गहराई से जाएं और पायथन में इंसर्शन सॉर्ट को लागू करें।

सॉर्टिंग फ़ंक्शन लिखें

हम एक पायथन फ़ंक्शन लिखकर शुरू करेंगे जो हमारा सॉर्ट करता है:

def sortNumbers(toSort):
    for number in range(1, len(toSort)):
        current_number = toSort[number]
        i = number - 1
        while i >= 0 and current_number < toSort[i]:
            toSort[i + 1] = toSort[i]
            i -= 1
        toSort[i + 1] = current_number

आइए देखते हैं कि यह कैसे काम करता है। हमारे sortNumbers फ़ंक्शन में हम एक पायथन फॉर लूप बनाते हैं जो सूची में हर संख्या के माध्यम से लूप करता है। फिर, हम सूची में पहले तत्व को पायथन वेरिएबल current_number को असाइन करके सॉर्ट किए गए मान के रूप में सेट करते हैं।

हम अनसॉर्ट की गई पायथन सूची में प्रत्येक आइटम के माध्यम से पुनरावृति करते हैं (current_number के बाद का प्रत्येक आइटम)। फिर, हम current_number की तुलना इसके बाईं ओर प्रत्येक संख्या से करते हैं। ऐसा होने के बाद, हम current_number का मान सूची में उसके बाद के तत्व के बराबर सेट करते हैं।

मुख्य प्रोग्राम लिखें

हमें एक मुख्य प्रोग्राम लिखना होगा जो हमारे इंसर्शन सॉर्ट को निष्पादित करता है:

numbers = [9, 4, 3, 5]
sortNumbers(numbers)
print(numbers)

हमारा कोड निम्न आउटपुट देता है:

[3, 4, 5, 9]

हमारी सूची आरोही क्रम में सॉर्ट की गई है! यहां तक पहुंचने पर बधाई।

पायथन इंसर्शन सॉर्ट: अवरोही क्रम

इंसर्शन सॉर्ट संख्याओं को अवरोही क्रम में सॉर्ट कर सकते हैं। इसे पूरा करने के लिए, आपको व्हाइल लूप में "less than" (<) चिह्न को उल्टा करना होगा और इसे greater than चिह्न बनाना होगा:

while i >= 0 and current_number > toSort[i]:

उपरोक्त उदाहरण में प्रतिस्थापित की गई कोड की यह पंक्ति सूची में आइटम्स को रिवर्स क्रम में सॉर्ट करेगी।

इंसर्शन सॉर्ट का उपयोग कब करना चाहिए?

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

इंसर्शन सॉर्ट बबल सॉर्ट से तेज़ हैं।

इंसर्शन सॉर्ट के बारे में जानना वैसे भी उपयोगी है। इंसर्शन सॉर्ट को लागू करने का तरीका जानने से आपको एक और प्रकार का सॉर्ट मिल जाता है जिसका आप उपयोग कर सकते हैं।

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

पायथन इंसर्शन सॉर्ट: जटिलता विश्लेषण

सभी एल्गोरिदम की तरह, सर्वोत्तम, सबसे खराब और औसत जटिलताओं को ध्यान में रखना महत्वपूर्ण है। इससे हमें इस बात की जानकारी मिलेगी कि एल्गोरिदम अपना काम करने में कितना प्रभावी है: इस मामले में, सूचियों को सॉर्ट करना।

सबसे खराब स्थिति और औसत जटिलताएं O(n²) हैं। इसका मतलब है कि जैसे-जैसे आप अपनी सूची में सॉर्ट करने के लिए अधिक मान जोड़ते हैं, एल्गोरिदम तेजी से धीमा होता जाएगा।

सर्वोत्तम स्थिति O(n) है। ऐसा तब होता है जब हम एल्गोरिदम को एक सॉर्ट की गई सूची पर चलाते हैं। एल्गोरिदम जांचता है कि आइटम्स सॉर्ट किए गए हैं और फिर चलना बंद कर देता है।

आप हमारे बिग O नोटेशन पर दो-भाग की श्रृंखला में एल्गोरिदम जटिलता को कैसे दर्शाते हैं, इसके बारे में अधिक जान सकते हैं।

निष्कर्ष

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

क्या आप अधिक पायथन प्रोग्रामिंग भाषा संसाधन ढूंढ रहे हैं? हमारे संपूर्ण How to Learn Python गाइड को देखें। आपको पायथन सीखने के बारे में शीर्ष युक्तियाँ और ऑनलाइन पाठ्यक्रमों, पुस्तकों, और अन्य संसाधनों की एक सूची मिलेगी।