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

इंसर्शन सॉर्ट ऐरे को सॉर्ट करने की एक सरल विधि है। इस तकनीक में, ऐरे को वर्चुअली सॉर्टेड और अनसॉर्टेड पार्ट में विभाजित किया जाता है। अनसॉर्टेड पार्ट से एक एलिमेंट चुना जाता है और इसे सॉर्टेड पार्ट में सही पोजीशन पर रखा जाता है।

• ऐरे एलिमेंट्स को 1 से n तक ट्रैवर्स किया जाता है।

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

• यदि पोजीशन i पर ऐरे एलिमेंट अपने पूर्ववर्ती से छोटा है, तो इसे तब तक बाएं शिफ्ट करने की आवश्यकता है जब तक कि हम इससे छोटा पूर्ववर्ती न पा लें या ऐरे में लेफ्टमोस्ट पोजीशन पर न पहुंच जाएं।

उदाहरण

हम एक उदाहरण की मदद से उपरोक्त विचार को अधिक स्पष्ट रूप से समझ सकते हैं। मान लीजिए हमारे पास निम्नलिखित ऐरे है -

हमें इंडेक्स 1 से ऐरे को ट्रैवर्स करना शुरू करना होगा (क्योंकि इंडेक्स 0 का कोई पूर्ववर्ती नहीं है)।

इंडेक्स 1 पर -

6 अपने पूर्ववर्ती से बड़ा है, इसलिए कुछ करने की आवश्यकता नहीं है।

इंडेक्स 2 पर -

1 अपने पूर्ववर्ती से छोटा है, इसलिए हमें इसे तब तक बाएं शिफ्ट करना होगा जब तक कि हम इससे छोटा पूर्ववर्ती न पा लें या इंडेक्स 0 पर न पहुंच जाएं। इस मामले में हम इंडेक्स 0 पर पहुंच जाएंगे।

इंडेक्स 3 पर -

इंडेक्स 4 पर -

2 को बाएं शिफ्ट करें, जब तक कि हम 2 से छोटा पूर्ववर्ती न पा लें।

इंडेक्स 5 पर -

5 को बाएं शिफ्ट करें, जब तक कि हम 5 से छोटा पूर्ववर्ती न पा लें।

इस प्रकार, हमें सॉर्टेड ऐरे प्राप्त होता है।

इंसर्शन सॉर्ट O(n^2) समय जटिलता और O(1) स्पेस जटिलता के साथ एक इन-प्लेस सॉर्टिंग एल्गोरिदम है।

उदाहरण

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i] #get each element
        j = i-1
        while j >= 0 and key < arr[j]: #keep shifting until reaching index 0 or getting an element smaller than key
            arr[j + 1] = arr[j]
            j=j-1
        arr[j + 1] = key

arr = [4,6,1,7,2,5]
insertionSort(arr)
for i in range(len(arr)):
    print (arr[i],end=" ")

आउटपुट

1 2 4 5 6 7