पायथन में सम्मिलन प्रकार क्या है?

इंसर्शन सॉर्ट एक सरणी को सॉर्ट करने का सरल तरीका है। इस तकनीक में, सरणी को वस्तुतः क्रमबद्ध और बिना छांटे हुए भाग में विभाजित किया जाता है। क्रमबद्ध भाग में से एक तत्व को चुना जाता है और क्रमबद्ध भाग में सही स्थिति में रखा जाता है।

• सरणी तत्वों को 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 &lit; 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