পাইথন প্রোগ্রাম: ইনসারশন সোর্ট অ্যালগরিদম

এই নিবন্ধে আমরা ইনসারশন সোর্ট এবং পাইথন ৩.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)

সকল ভেরিয়েবল গ্লোবাল ফ্রেমে ডিক্লেয়ার করা হয়েছে।

উপসংহার

এই নিবন্ধে আমরা পাইথন ৩.x-এ ইনসারশন সোর্ট এবং এর বাস্তবায়ন শিখেছি।