Insertion Sort: একটি সহজ এবং কার্যকরী সর্টিং অ্যালগোরিদম

Sorting বা সর্টিং প্রক্রিয়া প্রোগ্রামিংয়ে একটি সাধারণ সমস্যা। আমরা অনেক সময় ডেটা সাজানোর প্রয়োজন পড়ে যাতে আমরা সহজে প্রয়োজনীয় তথ্য পেতে পারি। এরকম একটি সহজ সর্টিং অ্যালগোরিদম হল Insertion Sort। এটি নতুন ইলিমেন্টগুলোকে সঠিক অবস্থানে রেখে আগের ডেটাগুলো সর্ট করে রাখে।

Insertion Sort কিভাবে কাজ করে?

এই অ্যালগোরিদমটি একটি ইনপুট লিস্টকে ধাপে ধাপে সাজায়। প্রতিটি ধাপে, লিস্টের একটি ইলিমেন্ট তুলে নেওয়া হয় এবং সেটিকে তার সঠিক স্থানে রাখার জন্য আগের ইলিমেন্টগুলোর সাথে তুলনা করা হয়। এভাবে নতুন ইলিমেন্ট সঠিক স্থানে বসে এবং আগের ইলিমেন্টগুলোকে ডান দিকে সরিয়ে দেয়।

Python কোড উদাহরণ

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [3, 8, 7, 5, 9, 4]
insertion_sort(arr)
print(arr)

    

কোডের ব্যাখ্যা

উপরের কোডটি একটি insertion_sort ফাংশন তৈরি করে যা একটি লিস্টকে সাজিয়ে দেয়। নিচে কোডটির ধাপে ধাপে ব্যাখ্যা দেওয়া হলো:

• Line 1: আমরা একটি insertion_sort নামে ফাংশন ডিফাইন করেছি যা arr নামে একটি লিস্ট ইনপুট হিসেবে গ্রহণ করে।
• Line 2: একটি লুপ চালানো হয়েছে যা ১ থেকে শুরু করে লিস্টের শেষ পর্যন্ত চলে। এটি key নামে একটি ভেরিয়েবল ধরে রাখে যা বর্তমান ইলিমেন্টটি ধরা হয়।
• Line 3: j নামক ভেরিয়েবলটি i - 1 মানে, অর্থাৎ আগের ইন্ডেক্স ধরে রাখে।
• Line 4: একটি while লুপ চলছে যতক্ষণ পর্যন্ত j শূন্য বা বড় এবং arr[j] এর মান key এর চেয়ে বেশি।
• Line 5: arr[j + 1] এ arr[j] এর মান রাখা হচ্ছে, অর্থাৎ বড় মানগুলো ডান দিকে সরানো হচ্ছে।
• Line 6: j এর মান এক কমিয়ে পূর্বের ইলিমেন্টে যাচ্ছি।
• Line 7: সঠিক স্থানে key বসানো হচ্ছে।

কাজের উদাহরণ

ধরুন, আমাদের ইনপুট লিস্টটি ছিল [3, 8, 7, 5, 9, 4]। নিচে প্রতিটি ধাপে লিস্টের পরিবর্তন দেখানো হয়েছে:

1. প্রথম ধাপে i = 1, key = 8। যেহেতু 3 ছোট 8 এর চেয়ে, তাই কোন পরিবর্তন হয় না।
2. দ্বিতীয় ধাপে i = 2, key = 7। 8 > 7, তাই 8 কে ডান দিকে সরিয়ে 7 তার সঠিক স্থানে বসানো হয়।
3. তৃতীয় ধাপে i = 3, key = 5। 8, 7 এবং 5 এর তুলনায় বড়, তাই এগুলো ডান দিকে সরে যায় এবং 5 সঠিক স্থানে বসে।
4. চতুর্থ ধাপে i = 4, key = 9। যেহেতু আগের ইলিমেন্টগুলো 9 এর চেয়ে ছোট, তাই কোন পরিবর্তন হয় না।
5. পঞ্চম ধাপে i = 5, key = 4। 9, 8, 7, 5 এগুলো 4 এর চেয়ে বড়, তাই সেগুলো ডান দিকে সরিয়ে 4 সঠিক স্থানে বসানো হয়।

চূড়ান্ত আউটপুট

শেষে প্রিন্ট করলে আমরা পাই: [3, 4, 5, 7, 8, 9]।

উপসংহার

Insertion Sort অ্যালগোরিদমটি সহজেই বোঝা যায় এবং ছোট আকারের ডেটা বা লিস্ট সর্ট করার জন্য বেশ উপযোগী। এটি একটি O(n^2) কমপ্লেক্সিটি সম্পন্ন অ্যালগোরিদম, অর্থাৎ বড় লিস্টের ক্ষেত্রে এটি একটু ধীরগতির হতে পারে। তবে এটি শেখার জন্য এবং সর্টিং অ্যালগোরিদমগুলোর ভিত্তি বুঝতে সাহায্য করে।

তুমি যদি আরও উন্নত সর্টিং অ্যালগোরিদম শিখতে চাও, তবে Khan Academy এর কন্টেন্ট দেখতে পারো। Happy coding!