पायथन प्रोग्राम: इंसर्शन सॉर्ट एल्गोरिदम

इस लेख में, हम पायथन 3.x या उससे पहले के संस्करण में इंसर्शन सॉर्ट के कार्यान्वयन के बारे में जानेंगे।

एल्गोरिदम

1. प्रत्येक पुनरावृत्ति पर सॉर्टेड सरणी को बढ़ाते हुए इनपुट तत्वों पर पुनरावृति करें।
2. वर्तमान तत्व की तुलना सॉर्टेड सरणी में उपलब्ध सबसे बड़े मान से करें।
3. यदि वर्तमान तत्व बड़ा है, तो इसे अपनी जगह पर छोड़ दें
   और अगले तत्व पर जाएं अन्यथा सॉर्टेड सरणी में इसकी सही स्थिति ढूंढें
   और इसे सरणी में उस स्थिति पर ले जाएं।
4. यह सॉर्टेड सरणी में वर्तमान तत्व से बड़े सभी तत्वों को
   एक स्थान दाएं शिफ्ट करके प्राप्त किया जाता है।

अब आइए एल्गोरिदम के दृश्य प्रतिनिधित्व को देखते हैं -

अब आइए कार्यान्वयन देखते हैं

उदाहरण

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # arr[0..i-1] के तत्वों को स्थानांतरित करें, जो key से बड़े हैं,
        # उनकी वर्तमान स्थिति से एक स्थान आगे
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

# मेन
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print("The sorted array is:")
for i in range(len(arr)):
    print(arr[i])

आउटपुट

The sorted array is: a i l o r t t u

समय जटिलता - O(n²)

सहायक स्थान - O(1)

सभी वेरिएबल्स ग्लोबल फ्रेम में घोषित हैं जैसा कि नीचे दिए गए चित्र में दिखाया गया है -

निष्कर्ष

इस लेख में, हमने पायथन 3.x या उससे पहले के संस्करण में इंसर्शन सॉर्ट और इसके कार्यान्वयन के बारे में सीखा।