Python में Insertion Sort
हर element को sorted हिस्से में insert करें।
में 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📥 पत्ते को खाली जगह में रखिएInsertion sort एक-एक आइटम करके sorted हिस्सा बनाता है। वह बड़े आइटम दाईं तरफ़ खिसकाता है और मौजूदा आइटम को खाली जगह में डाल देता है। सबसे बुरी स्थिति में यह O(n²) है, लेकिन लगभग sorted डेटा पर O(n) के करीब।
मुख्य बातें
for index in range(1, len(result)):दूसरे आइटम से शुरू होता है; अकेला आइटम पहले से sorted है।currentउस वैल्यू को रखता है जिसे डालना है, जब तक बड़ी वैल्यू खिसकती हैं।while position >= 0 and result[position] > current:हर बड़ी वैल्यू को एक जगह दाईं तरफ़ खिसकाता है।result[position + 1] = currentवैल्यू को उस खाली जगह में रखता है जो बनी थी।
इसका उपयोग कब करें?
- छोटी या लगभग sorted लिस्ट।
- नए आइटम आने पर लिस्ट को sorted बनाए रखना।
- तेज़ sorts के अंदर आख़िरी स्टेप के रूप में, जो छोटे टुकड़ों के लिए insertion sort पर चले जाते हैं।
कब ज़रूरत नहीं
- बड़ी random लिस्ट: खिसकाना धीमा हो जाता है, इसलिए
sorted()इस्तेमाल कीजिए। - बड़ी sorted लिस्ट में बार-बार आइटम डालना:
bisect.insortbinary search से जगह ढूँढता है।
Python में Insertion Sort Visualizer
हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
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]))
अपेक्षित आउटपुट
[1, 3, 4, 5, 9]
यह कैसे काम करता है
बड़े values को खिसकाकर insertion की जगह बनती है; nearly sorted data पर यह प्रभावी है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
लूप के अंदर 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 रिव्यू के साथ।
सभी चैलेंज