পাইথনে ইনসারশন সর্ট প্রোগ্রাম

এই আর্টিকেলে আমরা পাইথন ৩.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

# main
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-এ এর বাস্তবায়ন সম্পর্কে শিখেছি। বা এর আগের সংস্করণে।