पायथन प्रोग्राम में इंसर्शन सॉर्ट

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

एल्गोरिदम

• इनपुट एलिमेंट्स पर इटरेट करें और प्रत्येक इटरेशन में सॉर्टेड ऐरे को बढ़ाएं।
• वर्तमान एलिमेंट की तुलना सॉर्टेड ऐरे में उपलब्ध सबसे बड़े मान से करें।
• यदि वर्तमान एलिमेंट बड़ा है, तो यह एलिमेंट को उसकी जगह पर छोड़ देता है और अगले एलिमेंट पर चला जाता है अन्यथा यह सॉर्टेड ऐरे में अपनी सही स्थिति ढूंढता है और उसे उस स्थिति पर ऐरे में ले जाता है।
• यह सॉर्टेड ऐरे में उन सभी एलिमेंट्स को दाईं ओर शिफ्ट करके प्राप्त किया जाता है जो वर्तमान एलिमेंट से बड़े हैं, एक पोजीशन आगे।

आइए एल्गोरिदम का दृश्य प्रतिनिधित्व देखें:

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

उदाहरण

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 या इससे पहले इंसर्शन सॉर्ट और इसके कार्यान्वयन के बारे में सीखा।