Python एल्गोरिदम

Python में Insertion Sort

हर element को sorted हिस्से में insert करें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Insertion Sort क्या है?

समस्या क्या है

डेटा अक्सर लगभग sorted आता है, या एक-एक आइटम करके: scores की sorted लिस्ट में एक नया score जुड़ता है। सब कुछ फिर से sort करना बेकार है। Insertion sort इस स्थिति को बहुत अच्छे से संभालता है, और बहुत से लोग हाथ में ताश के पत्ते इसी तरह लगाते हैं।

ऐसे समझें

Insertion sort वैसे ही है जैसे आप हाथ में ताश के पत्ते लगाते हैं। आप एक बार में एक पत्ता उठाते हैं और उसे हर बड़े पत्ते के आगे से बाईं तरफ़ खिसकाते हैं, जब तक वह सही जगह न पहुँच जाए। उसके बाईं तरफ़ के पत्ते हमेशा क्रम में रहते हैं।

ताश के पत्तों से कोड तक
current = result[index]🃏 अगला पत्ता उठाइए
result[position] > current👈 क्या बाईं तरफ़ वाला पत्ता बड़ा है?
result[position + 1] = result[position]➡️ बड़े पत्ते को एक जगह दाईं तरफ़ खिसकाइए
result[position + 1] = current📥 पत्ते को खाली जगह में रखिए
बायाँ हिस्सा हमेशा sorted रहता है; हर नया आइटम उसमें डाला जाता है।
एक वाक्य में

Insertion sort एक-एक आइटम करके sorted हिस्सा बनाता है। वह बड़े आइटम दाईं तरफ़ खिसकाता है और मौजूदा आइटम को खाली जगह में डाल देता है। सबसे बुरी स्थिति में यह O(n²) है, लेकिन लगभग sorted डेटा पर O(n) के करीब।

मुख्य बातें

  1. for index in range(1, len(result)): दूसरे आइटम से शुरू होता है; अकेला आइटम पहले से sorted है।
  2. current उस वैल्यू को रखता है जिसे डालना है, जब तक बड़ी वैल्यू खिसकती हैं।
  3. while position >= 0 and result[position] > current: हर बड़ी वैल्यू को एक जगह दाईं तरफ़ खिसकाता है।
  4. result[position + 1] = current वैल्यू को उस खाली जगह में रखता है जो बनी थी।

इसका उपयोग कब करें?

  • छोटी या लगभग sorted लिस्ट।
  • नए आइटम आने पर लिस्ट को sorted बनाए रखना।
  • तेज़ sorts के अंदर आख़िरी स्टेप के रूप में, जो छोटे टुकड़ों के लिए insertion sort पर चले जाते हैं।

कब ज़रूरत नहीं

  • बड़ी random लिस्ट: खिसकाना धीमा हो जाता है, इसलिए sorted() इस्तेमाल कीजिए।
  • बड़ी sorted लिस्ट में बार-बार आइटम डालना: bisect.insort binary search से जगह ढूँढता है।

Python में Insertion Sort Visualizer

हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

[1, 3, 4, 5, 9]

यह कैसे काम करता है

बड़े values को खिसकाकर insertion की जगह बनती है; nearly sorted data पर यह प्रभावी है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

लूप के अंदर current वापस लिखना

वैल्यू सिर्फ़ एक बार रखनी है, सारी बड़ी वैल्यू खिसकने के बाद।

समस्या
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
सुधार
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज