इन्सर्शन सॉर्ट (Insertion sort)
इन्सर्शन सॉर्ट एल्गोरिदम चयन सॉर्ट एल्गोरिदम से काफी मिलता-जुलता है। यह बहुत सहज-समझ में आने वाला तरीका है, जिसमें ऐरे के बाएँ हिस्से को क्रमबद्ध रखा जाता है और उसके बाद दाएँ ओर बढ़ते हुए आख़िर तक ऐसे ही प्रोसेस किया जाता है।
विशेष रूप से, इन्सर्शन सॉर्ट एल्गोरिदम में हम ऐरे के सबसे बाएँ एलिमेंट से शुरू करते हैं और क्रमशः दाएँ ओर बढ़ते जाते हैं। जैसे ही हमें कोई ऐसा एलिमेंट दिखता है जो इसके पहले वाले एलिमेंट्स से छोटा है, हम उससे पहले के सभी एलिमेंट्स को एक-एक करके दाईं ओर शिफ्ट कर देते हैं ताकि उस एलिमेंट के लिए सही जगह बन सके, और फिर हम उसे वहीं रख देते हैं। उदाहरण के तौर पर, अगर हमारे पास ऐरे
[0, 2, 4, 1, 10, 8] है और हम फिलहाल 1 पर हैं, तो पहले हम 4 को शिफ्ट करेंगे, फिर 2 को, और उसके बाद 1 को 0 और 2 के बीच रख देंगे। इस तरह हमें [0, 1, 2, 4, 10, 8] मिल जाएगा। फिर हम अगले एलिमेंट 10 की ओर बढ़ेंगे और चूँकि यह बाईं ओर के सभी एलिमेंट्स से बड़ा है, इसलिए कुछ नहीं करेंगे। इसके बाद 8 को लेंगे और उसे 10 से पहले रखने के लिए 10 को दाईं ओर शिफ्ट कर देंगे, ताकि 8 को 4 और 10 के बीच जगह मिल सके।a = [...]
for i in range(1, len(a)): # दूसरे एलिमेंट से शुरू करें
while i > 0 and a[i] < a[i - 1]: # जब तक मौजूदा एलिमेंट छोटा है
a[i - 1], a[i] = a[i], a[i - 1] # मौजूदा एलिमेंट को पिछले एलिमेंट के साथ अदल-बदल करें
i -= 1 # मौजूदा एलिमेंट के इंडेक्स का ध्यान रखें
print(a)इन्सर्शन सॉर्ट एल्गोरिदम मौजूदा एलिमेंट को पहले से प्रोसेस किए हुए हिस्से में उसकी सही स्थिति में डालता है। सबसे ख़राब स्थिति (Worst case) में, अगर ऐरे के एलिमेंट घटते हुए क्रम में हों, तो हर बार नया एलिमेंट अपनी सही जगह पर रखने के लिए सभी पिछले एलिमेंट्स को शिफ्ट करना पड़ेगा। इस वजह से कुल मिलाकर ऑपरेशन्स करने पड़ सकते हैं।
आइए कुछ ऐरे लेकर एल्गोरिदम को स्टेप-बाय-स्टेप देखें:
[4, 1, -1, 0, 2, 8]
i = 1⇒ swap ⇒[1, 4, -1, 0, 2, 8]
i = 2⇒ swap ⇒[1, -1, 4, 0, 2, 8]⇒ swap ⇒[-1, 1, 4, 0, 2, 8]
i = 3⇒ do nothing
i = 4⇒ swap ⇒[-1, 1, 0, 4, 2, 8]⇒ swap ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒ do nothing
- print
[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
i = 1⇒ swap ⇒[5, 10, 1, -7]
i = 2⇒ swap ⇒[5, 1, 10, -7]⇒ swap ⇒[1, 5, 10, -7]
i = 3⇒ swap ⇒[1, 5, -7, 10]⇒ swap ⇒[1, -7, 5, 10]⇒ swap ⇒[-7, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 1⇒ do nothing
i = 2⇒ do nothing
i = 3⇒ do nothing
i = 4⇒ do nothing
चुनौती
दिए गए
n पूर्णांकों को इनक्रीज़िंग ऑर्डर में इन्सर्शन सॉर्ट का उपयोग करके सॉर्ट करें।इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ 1000) होता है, जो ऐरे में एलिमेंट्स की संख्या दर्शाता है।अगली पंक्ति में
n स्पेस-सेपरेटेड पूर्णांक दिए जाते हैं: ( ≤ ≤ ).आउटपुट
प्रोग्राम को इनपुट में मिले ऐरे को इनक्रीज़िंग ऑर्डर में प्रिंट करना चाहिए।
Examples
Input | Output |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB