পাইথন ইন্সারশন সর্ট: ধাপে ধাপে বাস্তবায়ন গাইড

ইন্সারশন সর্ট কী?

ইন্সারশন সর্ট (Insertion Sort) হলো একটি সহজ সর্টিং অ্যালগরিদম যা তোশের পাতা সাজানোর মতো কাজ করে। এটি লিস্টকে দুটি অংশে ভাগ করে: সর্টেড এবং আনসর্টেড। প্রতিটি ইটারেশনে আনসর্টেড লিস্ট থেকে একটি এলিমেন্ট নিয়ে সর্টেড লিস্ট-এ সঠিক পজিশনে ঢুকিয়ে দেওয়া হয়।

কিভাবে কাজ করে? (ভিজ্যুয়াল এক্সপ্লানেশন)

অ্যারে: [9, 4, 3, 5]

1. প্রথম এলিমেন্ট (৯) সর্টেড মনে করা হয়।
2. দ্বিতীয় এলিমেন্ট (৪) নেয়া হয়। ৪ < ৯, তাই ৪ কে ৯-এর আগে ঢুকিয়ে দেয়া হয় → [4, 9, 3, 5]
3. তৃতীয় এলিমেন্ট (৩) নেয়া হয়। ৩ < ৯ এবং ৩ < ৪ → [3, 4, 9, 5]
4. চতুর্থ এলিমেন্ট (৫) নেয়া হয়। ৫ < 9 কিন্তু ৫ > 4 → [3, 4, 5, 9]

ফাইনাল সর্টেড অ্যারে: [3, 4, 5, 9]

পাইথনে ইন্সারশন সর্ট বাস্তবায়ন

সর্টিং ফাংশন

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current = arr[i]
        j = i - 1
        # সর্টেড পার্টে সঠিক পজিশন খুঁজে বের করা
        while j >= 0 and current < arr[j]:
            arr[j + 1] = arr[j]  # এলিমেন্ট ডান দিকে শিফট
            j -= 1
        arr[j + 1] = current  # সঠিক পজিশনে বসানো
    return arr

মেইন প্রোগ্রাম

numbers = [9, 4, 3, 5]
sorted_numbers = insertion_sort(numbers)
print(sorted_numbers)  # আউটপুট: [3, 4, 5, 9]

ডিসেন্ডিং অর্ডারে সর্ট করা

بينما লুপের কন্ডিশন পরিবর্তন করুন:

while j >= 0 and current > arr[j]:  # '>' চিহ্ন ব্যবহার করুন
    arr[j + 1] = arr[j]
    j -= 1

কখন ইন্সারশন সর্ট ব্যবহার করবেন?

• ছোট সাইজের লিস্ট (n < 50) সর্ট করার জন্য।
• প্রায় সর্টেড লিস্ট (Nearly sorted data) সর্ট করার জন্য।
• অনলাইন অ্যালগরিদম হিসেবে (ডেটা স্ট্রিম আসার সাথে সাথে সর্ট করতে)।

বড় লিস্টের জন্য মার্জ সর্ট বা কুইক সর্ট ব্যবহার করুন (O(n log n))।

টাইম কমপ্লেক্সিটি বিশ্লেষণ

নিষ্কর্ষ

ইন্সারশন সর্ট হলো বুঝতে সহজ, কম মেমরি ব্যবহারকারী এবং ছোট বা প্রায়-সর্টেড ডেটার জন্য দক্ষ একটি সর্টিং অ্যালগরিদম। এটি শিখলে আরও জটিল সর্টিং অ্যালগরিদম (যেমন মার্জ সর্ট) বোঝা সহজ হয়।