Selection Sort অ্যালগরিদম: সহজ ভাষায় বোঝা

Selection Sort একটি সহজ এবং জনপ্রিয় সোর্টিং অ্যালগরিদম যা ছোট ডেটা সেটের জন্য ভালো কাজ করে। এটি একটি ইন-প্লেস সোর্টিং পদ্ধতি যেখানে অতিরিক্ত মেমোরি ব্যবহার হয় না। Selection Sort এর প্রধান ধারণা হল প্রতিবার সিকুয়েন্স থেকে সবচেয়ে ছোট উপাদানটি খুঁজে বের করে সঠিক অবস্থানে বসানো।

কীভাবে Selection Sort কাজ করে?

Selection Sort অ্যালগরিদমের মাধ্যমে একটি অ্যারের উপাদানগুলোকে ছোট থেকে বড় ক্রমে সাজাতে হলে নিম্নলিখিত ধাপগুলো অনুসরণ করতে হয়:

• প্রথমে অ্যারের প্রথম উপাদান থেকে শুরু করি এবং ধরে নিই এটি সবচেয়ে ছোট উপাদান।
• এরপর বাকি উপাদানগুলোর সাথে তুলনা করে সবচেয়ে ছোট উপাদান খুঁজে বের করি।
• সবচেয়ে ছোট উপাদানটি খুঁজে পেলে, সেটিকে বর্তমান অবস্থানের সাথে অদলবদল করি।
• এরপর পরবর্তী উপাদান থেকে আবার একই প্রক্রিয়া চালাই যতক্ষণ না সব উপাদান সঠিকভাবে সাজানো হয়ে যায়।

Selection Sort এর উদাহরণ কোড

def selection_sort(arr):

    # প্রতিটি উপাদানের জন্য

    for i in range(len(arr)):

        # ধরে নিই যে i তম উপাদানটাই সবচেয়ে ছোট

        min_idx = i

        # i এর পরবর্তী সব উপাদানের জন্য

        for j in range(i + 1, len(arr)):

            # যদি j তম উপাদানটি min_idx তে থাকা উপাদানের চেয়ে ছোট হয়

            if arr[j] < arr[min_idx]:

                # তাহলে min_idx আপডেট করে দেই

                min_idx = j

        # সবচেয়ে ছোট উপাদানটিকে বর্তমান i তম স্থানে বসাই

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# উদাহরণ:

numbers = [5, 3, 8, 6, 7, 2]

selection_sort(numbers)

print("Sorted array:", numbers)



    

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

উপরের কোডে, selection_sort ফাংশনটি একটি অ্যারে গ্রহণ করে এবং তা সাজানো অবস্থায় রিটার্ন করে। কোডটি মূলত দুটি লুপ ব্যবহার করে:

• প্রথম লুপটি i এর মান বাড়িয়ে অ্যারের প্রতিটি উপাদান পরিদর্শন করে।
• দ্বিতীয় লুপটি j এর সাহায্যে i এর পরবর্তী উপাদানগুলোকে পরিদর্শন করে সবচেয়ে ছোট উপাদানটি খুঁজে বের করে।
• যদি কোনো উপাদান min_idx এর চেয়ে ছোট হয়, তবে min_idx আপডেট করা হয়।
• সবচেয়ে ছোট উপাদান পাওয়ার পর, i তম উপাদানের সাথে অদলবদল করা হয়।

আউটপুট

উপরের কোডটি রান করলে আউটপুট হবে:

Sorted array: [2, 3, 5, 6, 7, 8]

Selection Sort এর জটিলতা

Selection Sort এর সময় জটিলতা হল O(n2), যেখানে n হল অ্যারের দৈর্ঘ্য। কারণ প্রতিটি উপাদান নির্বাচন এবং স্থানান্তর করতে n বার কম্প্যারিজন করতে হয়। তাই, এটি বড় ডেটা সেটের জন্য ততটা কার্যকর নয়। তবে, ছোট ডেটা সেটের জন্য এটি একটি সহজ ও বোধগম্য সমাধান।

উপসংহার

Selection Sort একটি সহজ এবং প্রাথমিক অ্যালগরিদম হলেও, এটি আমাদের সঠিকভাবে সিকুয়েন্স সোজাতে সাহায্য করে। বিশেষ করে, যখন শিখছি কীভাবে সিকুয়েন্সিং কাজ করে, তখন Selection Sort বোঝা অনেক সহজ এবং কার্যকরী। আশা করি এই ব্লগটি আপনাকে Selection Sort সম্পর্কে একটি পরিষ্কার ধারণা দিতে পেরেছে।